如何在没有正则表达式的情况下实现语言解释器？
How to implement a language interpreter without regular expressions?
我正在尝试编写一种解释型编程语言，它将读取文件并输出类似字节码的格式，然后可以由虚拟机执行。
我的原计划是：
- 首先将文件内容加载到我的解释器内存中，
- 阅读每一行（单词定义为一系列字母后跟 space 或转义字符），
- 使用正则表达式，确定单词的参数，
- 例如
IF myvalue = 5 THEN会变成IFmyvalue5,
- 将每个单词转换为字节形式（即
IF 将变为 0x09），
- 一个一个地执行这些字节（因为执行者会理解
IF 或 0x09 后面跟着两个字节。
有人告诉我，正则表达式是执行此操作的糟糕方法，但我不确定这是实现解释性语言的好方法还是坏方法。
这主要是为了体验，所以我不介意它是否对性能不友好，但这将是一个好处。
实现我的解释器的最佳方式是什么，是否有任何示例（用普通的旧 C 编写）？
正如其他人所提到的，正则表达式没有任何问题。这是一个典型的路径：
- 将您的源文件解析为标记
- 从已解析的标记流中生成抽象语法树
- 遍历 AST 生成字节码
Flex/bison 是 1/2 的好工具。
您可能还需要某种符号 table 来定义变量。
许多编译器设计课程最终会为 c 语言的某些子集实现编译器，您可以尝试查看开放课件类型站点以获取实际的 class。
人们之所以告诉您正则表达式不是这种情况的最佳选择，是因为正则表达式需要更多时间来求值，而且正则表达式语言有许多限制和怪癖，因此不适合许多应用程序。
您应该知道，这只是许多程序员（包括我自己）的下意识反应，而不管正则表达式是否真的适合应用程序。这源于人们试图对正则表达式做太多事情，例如试图解析 HTML.
许多编译器使用基本的单遍标记化算法。分词器对什么可以用作定界符、常量和标识符应该如何处理等有一个非常基本的想法。然后分词器将快速遍历输入并发出一串可以轻松解析的标记。
对于解析令牌等基本应用程序，使用正则表达式带来的相对较小的损失并不值得担心。然而，正如我所说，有时正则表达式的工作方式存在一些特殊性，这可能会限制您的分词器可以做的事情，尽管通常可以将这些工作卸载到编译器管道中的稍后位置。不过，分词器应该做的所有事情都应该可以用标准正则表达式表示。
应该注意的是，当您在代码中直接涉及正则表达式时，事情可能会变得有点棘手。您必须确定应如何将正则表达式应用于输入、在何处描述输入等。您还将招致编译和评估正则表达式的惩罚。
有一些项目，例如 lex，它们使用正则表达式，因为它们提供了一种简单、简洁的方式来描述语法，然后它可以在内部以选择的任何表示形式使用它.他们还将为您处理所有的胶合逻辑，您只需通过正则表达式描述它应该使用的语法。
当使用这样的生成器时，它可以将任何正则表达式更改为表示表达式实际含义的代码。如果它看到表达式 [0-9]，它可以将其替换为对 isdigit 的调用、等效的 switch 语句或其他表示形式。这使得生成的代码比任何内联使用正则表达式的效率都高得多。
所以我的想法是：如果你想使用正则表达式来解析你的语言，一路走下去，为 flex/lex 创建一个扫描器描述来为你生成分词器.但是，如果您实际上完全是自己编写的，那么您最好采用逻辑上更简单的方法，例如我所描述的方法。
我认为编写一个不使用正则表达式的示例分词器会很有趣，所以就在这里。我用类似 C 的 C++ 编写了它。我使用的唯一 C++ 功能是标准向量和字符串，但我这样做的方式让您可以轻松地加入 C 变体。
#include <vector>
#include <ctype.h>
#include <string>
typedef std::vector<std::string> string_list;
typedef std::vector<long long > int_list;
typedef std::vector<long double> float_list;
std::string substr(const char* value, size_t length){
std::string v;
v.resize(length);
memcpy(&v[0], value, length * sizeof(char));
return v;
}
long long string_to_int(const char* value, size_t length){
return atoll(substr(value, length).c_str());
}
long double string_to_float(const char* value, size_t length){
return atof(substr(value, length).c_str());
}
void int_list_add(int_list& list, long long value){
list.push_back(value);
}
void string_list_add(string_list& list, const char* value, size_t length){
list.push_back(substr(value, length));
}
void float_list_add(float_list& list, long double value){
list.push_back(value);
}
size_t int_list_last(int_list& list){
return list.size();
}
size_t string_list_last(string_list& list){
return list.size();
}
size_t float_list_last(float_list& list){
return list.size();
}
typedef struct{
string_list identifiers;
string_list constants_string;
int_list constants_int;
float_list constants_float;
size_t id;
} *state, state_value;
state tok_state_create(){
state ret = new state_value;
ret->id = 0;
return ret;
}
void tok_state_destroy(state t_state){
delete t_state;
}
const char* tok_state_read_identifier(state t_state, size_t id){
return t_state->identifiers[id - 1].c_str();
}
const char* tok_state_read_string(state t_state, size_t id){
return t_state->constants_string[id - 1].c_str();
}
long long tok_state_read_int(state t_state, size_t id){
return t_state->constants_int[id - 1];
}
long double tok_state_read_float(state t_state, size_t id){
return t_state->constants_float[id - 1];
}
const char* punct_tokens[] = { "Not A Token (Dummy)",
".", ",", "<", "<<", ">", ">>",
";", "+", "-", "/", "*", "!", "%", "^",
"&", "(", ")", "=", "==", "[", "]", "{",
"}", "?", ":", "|", "||", "&&", "~", 0
};
const char* key_tokens[] = { "Not A Token (Dummy)",
"if", "while", "do", "then", "end", 0
};
typedef enum{
TOK_TYPE_INTEGER = 500,
TOK_TYPE_FLOAT,
TOK_TYPE_STRING,
TOK_TYPE_IDENTIFIER,
TOK_TYPE_NONE
} tok_type;
const char* get_token_from_id(size_t id){
if (id < 100){
return punct_tokens[id];
}
if (id < 200){
return key_tokens[id - 100];
}
if (id >= 500){
switch (id){
case TOK_TYPE_INTEGER: return "Integer Constant";
case TOK_TYPE_FLOAT: return "Float Constant ";
case TOK_TYPE_STRING: return "String Constant ";
case TOK_TYPE_IDENTIFIER: return "Identifier ";
case TOK_TYPE_NONE: return "Unknown ";
default:
break;
}
}
return "Not A Token (Dummy)";
}
int is_identifier_char(char c){
if (isalpha(c) || c == '_'){
return 1;
}
return 0;
}
size_t read_punct_token(const char* input, size_t size){
size_t max_len = 0;
size_t token_id = 0;
for (size_t i = 1; punct_tokens[i] != 0; ++i){
size_t len = strlen(punct_tokens[i]);
if (len > max_len && len <= size && strncmp(punct_tokens[i], input, len) == 0){
max_len = len;
if (i == 1 && size > 1 && isdigit(input[1])){
return 0; //Special case for floats
}
token_id = i;
}
}
return token_id;
}
size_t read_key_token(const char* input, size_t size){
size_t max_len = 0;
size_t token_id = 0;
for (size_t i = 1; key_tokens[i] != 0; ++i){
size_t len = strlen(key_tokens[i]);
if (len > max_len && len <= size && strncmp(key_tokens[i], input, len) == 0){
max_len = len;
token_id = i + 100;
}
}
return token_id;
}
size_t is_punct_token_char(char c){
for (size_t i = 1; punct_tokens[i] != 0; ++i){
if (punct_tokens[i][0] == c){
return 1;
}
}
return 0;
}
void add_token(state t_state, tok_type type, const char* string, size_t length){
switch (type){
case TOK_TYPE_INTEGER:
int_list_add(t_state->constants_int, string_to_int(string, length));
t_state->id = int_list_last(t_state->constants_int);
break;
case TOK_TYPE_FLOAT:
float_list_add(t_state->constants_float, string_to_float(string, length));
t_state->id = float_list_last(t_state->constants_float);
break;
case TOK_TYPE_STRING:
string_list_add(t_state->constants_string, string, length);
t_state->id = string_list_last(t_state->constants_string);
break;
case TOK_TYPE_IDENTIFIER:
string_list_add(t_state->identifiers, string, length);
t_state->id = string_list_last(t_state->identifiers);
break;
default:
//Do some error here
break;
}
}
size_t get_token(state t_state, char** input, size_t *size){
if (t_state->id != 0){
size_t id = t_state->id;
t_state->id = 0;
return id;
}
char* base = *input;
size_t padding = 0;
size_t length = 0;
tok_type type = TOK_TYPE_NONE;
while (*size > 0){
if (isspace(*base)){
base++;
(*size)--;
}
else{
break;
}
}
size_t tok = read_punct_token(base, *size);
if (tok){
size_t len = +strlen(get_token_from_id(tok));
*input = base + len;
*size -= len;
return tok;
}
tok = read_key_token(base, *size);
if (tok){
size_t len = +strlen(get_token_from_id(tok));
*input = base + len;
*size -= len;
return tok;
}
while (*size - length > 0){
if (length == 0 && type == TOK_TYPE_NONE){
if (is_identifier_char(*base)){
type = TOK_TYPE_IDENTIFIER;
length++;
}
else if (*base == '"'){
type = TOK_TYPE_STRING;
padding = 1;
base++;
(*size)--;
}
else if (*base == '.' && *size > 1 && isdigit(base[1])){
type = TOK_TYPE_FLOAT;
}
else if (isdigit(*base)){
type = TOK_TYPE_INTEGER;
}
else if (is_punct_token_char(*base)){
tok = read_punct_token(base, *size);
if (tok){
size_t len = strlen(punct_tokens[tok]);
*input += len;
*size -= len;
return tok;
}
else{
//do error
}
}
}
else{
if (!isspace(base[length]) || type == TOK_TYPE_STRING){
switch (type){
case TOK_TYPE_INTEGER:
if (isdigit(base[length])){
length++;
continue;
}
else if (base[length] == '.' || tolower(base[length]) == 'e'){
type = TOK_TYPE_FLOAT;
length++;
continue;
}
break;
case TOK_TYPE_FLOAT:
if (isdigit(base[length]) || base[length] == '.' || base[length] == 'e'){
length++;
continue;
}
break;
case TOK_TYPE_STRING:
if (base[length] != '"'){
length++;
continue;
}
break;
case TOK_TYPE_IDENTIFIER:
if (is_identifier_char(base[length])){
length++;
continue;
}
break;
default:
break;
}
}
//We only get here if this is a space or any of the switch cases didn't continue.
add_token(t_state, type, base, length);
*input = base + length + padding;
*size -= length + padding;
return type;
}
}
*input = base + length + padding;
*size -= length + padding;
return 0;
}
int main(){
const char* input = "if(1+1==4)then print\"hi!\";end";
state s = tok_state_create();
size_t size = strlen(input);
size_t token;
size_t token_prev = 0;
printf("Token\tMeaning\n\n");
while ((token = get_token(s, (char**)&input, &size)) != 0){
if (token_prev < 500){
if (token < 500){
printf("%d\t%s\n", token, get_token_from_id(token));
}
else{
printf("%d\t%s #", token, get_token_from_id(token));
}
}
else{
printf("%d\t", token);
switch (token_prev){
case TOK_TYPE_IDENTIFIER: printf("%s\n", tok_state_read_identifier(s, token)); break;
case TOK_TYPE_STRING: printf("%s\n", tok_state_read_string(s, token)); break;
case TOK_TYPE_INTEGER: printf("%d\n", tok_state_read_int(s, token)); break;
case TOK_TYPE_FLOAT: printf("%f\n", tok_state_read_float(s, token)); break;
}
}
token_prev = token;
}
tok_state_destroy(s);
}
这将打印：
Token Meaning
101 if
16 (
500 Integer Constant #1 1
8 +
500 Integer Constant #2 1
19 ==
500 Integer Constant #3 4
17 )
104 then
503 Identifier #1 print
502 String Constant #1 hi!
7 ;
105 end
正如其他答案所说，正则表达式本身没有任何问题。但不仅如此，正则表达式是字符级语法的自然表示。
所有主要（以及许多（大多数？）次要语言）都使用正则表达式来定义不同输入标记的外观，至少作为设计语言的形式主义。
但正则表达式库提供的某些技巧确实可能会降低性能。这是因为很多事情，比如反向引用，必须由功能较弱的自动机来实现，而不是更 纯 的正则表达式。
正则表达式（没有反向引用等花哨的东西）可以转换为有限自动机或状态机，并且可以用更简单的方式实现（即 更快）控制功能。
至少，为了提高效率，您应该尝试预编译您的语言定义表达式并使用编译后的匹配器对象，而不是每次都动态构造一个新的匹配器对象。如果你的正则表达式库不提供这个，也许是时候去图书馆购物，或者阅读自动机理论。
复杂语言 ("has expressions with (...) or compound nested statements like do-while, if-then-else") 的任何解释器或编译器都需要您构建解析器来提取代码的（通常是递归的）结构。
你在这里得到了很多答案"regular expressions are good for tokens"。是的，在许多 class 内置的编译器和解释器中，人们编写正则表达式来描述单个标记（标识符、关键字、数字和字符串常量、注释）的形状，并将它们交给词法分析器生成器（如 Flex 或many others) 将这些组合成一个高效的有限状态机。这是可行的，因为令牌的 "syntax" 几乎总是非常简单。这种非常简单意味着您可以自己编写一个令牌词法分析器，并为中小型语言产生实际结果。 （在某些时候（例如，COBOL）语言的庞大规模开始让你不知所措，如果你想保持理智，很难避免使用词法分析器生成器）。
没有讨论的是真实的解析，假设我们已经以某种方式构建了令牌，发现结构。对令牌使用正则表达式不是解析。正则表达式不能用于解析；他们无法识别嵌套结构，而这是那些 "sophisticated" 构造所需要的。 不熟悉解析的人会反复犯这个错误。
如果你想成功，你需要学习如何构建解析器。
对于复杂的语言，有解析器生成器（YACC、JavaCC、many others），类似于词法分析器生成器，它将采用 BNF 并为您生成解析器。如果你想用这样的工具编写一个编译器，你通常将 解析器操作 附加到语法规则识别点，通常是为以后的处理构建树。
您也可以 hand-code a parser for modest size languages. 这是一组相互递归的过程，每个语法规则一个，用于分析代码（使用递归来处理嵌套结构）。您还可以将解析操作附加到过程。由于这些过程识别语法结构，这实际上与您在使用解析器生成器时应用的技巧本质上是相同的。可以简单地扩展此方案以处理令牌的 "parsing"(lexing)。如果你完全沿着这条路走下去，那么任何地方都没有正则表达式。
可以通过在语法规则识别中执行解释器操作来构建解释器 places/in 手动编码的递归解析过程。它不会 运行 很快，因为它会不断地重新解析源代码。
不如建一个(abstract) syntax tree (AST) representing the program, and then build and interpreter that crawls the AST to execute it。 AST 是通过将树构建操作附加为解析器操作来构建的。
如果你想生成字节码，那么你有一个classic 代码生成问题。这些通常最好通过构建 AST 来解决，几乎像解释器一样遍历 AST，并吐出旨在在每个点实现解释器目的的字节代码。您可以通过在解析器操作中生成字节代码来构建即时代码生成器。以这种方式生成 "good" 代码比较困难，因为代码生成器看不到足够的上下文来很好地处理特殊情况。
您可以摸索着完成所有这些。最好的方法是获得一本编译器书籍，或者使用编译器 class。那么这一切都会清楚很多。当然，如果您摸索着解决这个问题，您将更好地理解人们用来执行此操作的编译器的种类。 （Google 我关于 "Life After Parsing" 的文章）。
我正在尝试编写一种解释型编程语言，它将读取文件并输出类似字节码的格式，然后可以由虚拟机执行。
我的原计划是：
- 首先将文件内容加载到我的解释器内存中，
- 阅读每一行（单词定义为一系列字母后跟 space 或转义字符），
- 使用正则表达式，确定单词的参数，
- 例如
IF myvalue = 5 THEN会变成IFmyvalue5, - 将每个单词转换为字节形式（即
IF将变为0x09）， - 一个一个地执行这些字节（因为执行者会理解
IF或0x09后面跟着两个字节。
有人告诉我，正则表达式是执行此操作的糟糕方法，但我不确定这是实现解释性语言的好方法还是坏方法。
这主要是为了体验，所以我不介意它是否对性能不友好，但这将是一个好处。
实现我的解释器的最佳方式是什么，是否有任何示例（用普通的旧 C 编写）？
正如其他人所提到的，正则表达式没有任何问题。这是一个典型的路径：
- 将您的源文件解析为标记
- 从已解析的标记流中生成抽象语法树
- 遍历 AST 生成字节码
Flex/bison 是 1/2 的好工具。
您可能还需要某种符号 table 来定义变量。
许多编译器设计课程最终会为 c 语言的某些子集实现编译器，您可以尝试查看开放课件类型站点以获取实际的 class。
人们之所以告诉您正则表达式不是这种情况的最佳选择，是因为正则表达式需要更多时间来求值，而且正则表达式语言有许多限制和怪癖，因此不适合许多应用程序。
您应该知道，这只是许多程序员（包括我自己）的下意识反应，而不管正则表达式是否真的适合应用程序。这源于人们试图对正则表达式做太多事情，例如试图解析 HTML.
许多编译器使用基本的单遍标记化算法。分词器对什么可以用作定界符、常量和标识符应该如何处理等有一个非常基本的想法。然后分词器将快速遍历输入并发出一串可以轻松解析的标记。
对于解析令牌等基本应用程序，使用正则表达式带来的相对较小的损失并不值得担心。然而，正如我所说，有时正则表达式的工作方式存在一些特殊性，这可能会限制您的分词器可以做的事情，尽管通常可以将这些工作卸载到编译器管道中的稍后位置。不过，分词器应该做的所有事情都应该可以用标准正则表达式表示。
应该注意的是，当您在代码中直接涉及正则表达式时，事情可能会变得有点棘手。您必须确定应如何将正则表达式应用于输入、在何处描述输入等。您还将招致编译和评估正则表达式的惩罚。
有一些项目，例如 lex，它们使用正则表达式，因为它们提供了一种简单、简洁的方式来描述语法，然后它可以在内部以选择的任何表示形式使用它.他们还将为您处理所有的胶合逻辑，您只需通过正则表达式描述它应该使用的语法。
当使用这样的生成器时，它可以将任何正则表达式更改为表示表达式实际含义的代码。如果它看到表达式 [0-9]，它可以将其替换为对 isdigit 的调用、等效的 switch 语句或其他表示形式。这使得生成的代码比任何内联使用正则表达式的效率都高得多。
所以我的想法是：如果你想使用正则表达式来解析你的语言，一路走下去，为 flex/lex 创建一个扫描器描述来为你生成分词器.但是，如果您实际上完全是自己编写的，那么您最好采用逻辑上更简单的方法，例如我所描述的方法。
我认为编写一个不使用正则表达式的示例分词器会很有趣，所以就在这里。我用类似 C 的 C++ 编写了它。我使用的唯一 C++ 功能是标准向量和字符串，但我这样做的方式让您可以轻松地加入 C 变体。
#include <vector>
#include <ctype.h>
#include <string>
typedef std::vector<std::string> string_list;
typedef std::vector<long long > int_list;
typedef std::vector<long double> float_list;
std::string substr(const char* value, size_t length){
std::string v;
v.resize(length);
memcpy(&v[0], value, length * sizeof(char));
return v;
}
long long string_to_int(const char* value, size_t length){
return atoll(substr(value, length).c_str());
}
long double string_to_float(const char* value, size_t length){
return atof(substr(value, length).c_str());
}
void int_list_add(int_list& list, long long value){
list.push_back(value);
}
void string_list_add(string_list& list, const char* value, size_t length){
list.push_back(substr(value, length));
}
void float_list_add(float_list& list, long double value){
list.push_back(value);
}
size_t int_list_last(int_list& list){
return list.size();
}
size_t string_list_last(string_list& list){
return list.size();
}
size_t float_list_last(float_list& list){
return list.size();
}
typedef struct{
string_list identifiers;
string_list constants_string;
int_list constants_int;
float_list constants_float;
size_t id;
} *state, state_value;
state tok_state_create(){
state ret = new state_value;
ret->id = 0;
return ret;
}
void tok_state_destroy(state t_state){
delete t_state;
}
const char* tok_state_read_identifier(state t_state, size_t id){
return t_state->identifiers[id - 1].c_str();
}
const char* tok_state_read_string(state t_state, size_t id){
return t_state->constants_string[id - 1].c_str();
}
long long tok_state_read_int(state t_state, size_t id){
return t_state->constants_int[id - 1];
}
long double tok_state_read_float(state t_state, size_t id){
return t_state->constants_float[id - 1];
}
const char* punct_tokens[] = { "Not A Token (Dummy)",
".", ",", "<", "<<", ">", ">>",
";", "+", "-", "/", "*", "!", "%", "^",
"&", "(", ")", "=", "==", "[", "]", "{",
"}", "?", ":", "|", "||", "&&", "~", 0
};
const char* key_tokens[] = { "Not A Token (Dummy)",
"if", "while", "do", "then", "end", 0
};
typedef enum{
TOK_TYPE_INTEGER = 500,
TOK_TYPE_FLOAT,
TOK_TYPE_STRING,
TOK_TYPE_IDENTIFIER,
TOK_TYPE_NONE
} tok_type;
const char* get_token_from_id(size_t id){
if (id < 100){
return punct_tokens[id];
}
if (id < 200){
return key_tokens[id - 100];
}
if (id >= 500){
switch (id){
case TOK_TYPE_INTEGER: return "Integer Constant";
case TOK_TYPE_FLOAT: return "Float Constant ";
case TOK_TYPE_STRING: return "String Constant ";
case TOK_TYPE_IDENTIFIER: return "Identifier ";
case TOK_TYPE_NONE: return "Unknown ";
default:
break;
}
}
return "Not A Token (Dummy)";
}
int is_identifier_char(char c){
if (isalpha(c) || c == '_'){
return 1;
}
return 0;
}
size_t read_punct_token(const char* input, size_t size){
size_t max_len = 0;
size_t token_id = 0;
for (size_t i = 1; punct_tokens[i] != 0; ++i){
size_t len = strlen(punct_tokens[i]);
if (len > max_len && len <= size && strncmp(punct_tokens[i], input, len) == 0){
max_len = len;
if (i == 1 && size > 1 && isdigit(input[1])){
return 0; //Special case for floats
}
token_id = i;
}
}
return token_id;
}
size_t read_key_token(const char* input, size_t size){
size_t max_len = 0;
size_t token_id = 0;
for (size_t i = 1; key_tokens[i] != 0; ++i){
size_t len = strlen(key_tokens[i]);
if (len > max_len && len <= size && strncmp(key_tokens[i], input, len) == 0){
max_len = len;
token_id = i + 100;
}
}
return token_id;
}
size_t is_punct_token_char(char c){
for (size_t i = 1; punct_tokens[i] != 0; ++i){
if (punct_tokens[i][0] == c){
return 1;
}
}
return 0;
}
void add_token(state t_state, tok_type type, const char* string, size_t length){
switch (type){
case TOK_TYPE_INTEGER:
int_list_add(t_state->constants_int, string_to_int(string, length));
t_state->id = int_list_last(t_state->constants_int);
break;
case TOK_TYPE_FLOAT:
float_list_add(t_state->constants_float, string_to_float(string, length));
t_state->id = float_list_last(t_state->constants_float);
break;
case TOK_TYPE_STRING:
string_list_add(t_state->constants_string, string, length);
t_state->id = string_list_last(t_state->constants_string);
break;
case TOK_TYPE_IDENTIFIER:
string_list_add(t_state->identifiers, string, length);
t_state->id = string_list_last(t_state->identifiers);
break;
default:
//Do some error here
break;
}
}
size_t get_token(state t_state, char** input, size_t *size){
if (t_state->id != 0){
size_t id = t_state->id;
t_state->id = 0;
return id;
}
char* base = *input;
size_t padding = 0;
size_t length = 0;
tok_type type = TOK_TYPE_NONE;
while (*size > 0){
if (isspace(*base)){
base++;
(*size)--;
}
else{
break;
}
}
size_t tok = read_punct_token(base, *size);
if (tok){
size_t len = +strlen(get_token_from_id(tok));
*input = base + len;
*size -= len;
return tok;
}
tok = read_key_token(base, *size);
if (tok){
size_t len = +strlen(get_token_from_id(tok));
*input = base + len;
*size -= len;
return tok;
}
while (*size - length > 0){
if (length == 0 && type == TOK_TYPE_NONE){
if (is_identifier_char(*base)){
type = TOK_TYPE_IDENTIFIER;
length++;
}
else if (*base == '"'){
type = TOK_TYPE_STRING;
padding = 1;
base++;
(*size)--;
}
else if (*base == '.' && *size > 1 && isdigit(base[1])){
type = TOK_TYPE_FLOAT;
}
else if (isdigit(*base)){
type = TOK_TYPE_INTEGER;
}
else if (is_punct_token_char(*base)){
tok = read_punct_token(base, *size);
if (tok){
size_t len = strlen(punct_tokens[tok]);
*input += len;
*size -= len;
return tok;
}
else{
//do error
}
}
}
else{
if (!isspace(base[length]) || type == TOK_TYPE_STRING){
switch (type){
case TOK_TYPE_INTEGER:
if (isdigit(base[length])){
length++;
continue;
}
else if (base[length] == '.' || tolower(base[length]) == 'e'){
type = TOK_TYPE_FLOAT;
length++;
continue;
}
break;
case TOK_TYPE_FLOAT:
if (isdigit(base[length]) || base[length] == '.' || base[length] == 'e'){
length++;
continue;
}
break;
case TOK_TYPE_STRING:
if (base[length] != '"'){
length++;
continue;
}
break;
case TOK_TYPE_IDENTIFIER:
if (is_identifier_char(base[length])){
length++;
continue;
}
break;
default:
break;
}
}
//We only get here if this is a space or any of the switch cases didn't continue.
add_token(t_state, type, base, length);
*input = base + length + padding;
*size -= length + padding;
return type;
}
}
*input = base + length + padding;
*size -= length + padding;
return 0;
}
int main(){
const char* input = "if(1+1==4)then print\"hi!\";end";
state s = tok_state_create();
size_t size = strlen(input);
size_t token;
size_t token_prev = 0;
printf("Token\tMeaning\n\n");
while ((token = get_token(s, (char**)&input, &size)) != 0){
if (token_prev < 500){
if (token < 500){
printf("%d\t%s\n", token, get_token_from_id(token));
}
else{
printf("%d\t%s #", token, get_token_from_id(token));
}
}
else{
printf("%d\t", token);
switch (token_prev){
case TOK_TYPE_IDENTIFIER: printf("%s\n", tok_state_read_identifier(s, token)); break;
case TOK_TYPE_STRING: printf("%s\n", tok_state_read_string(s, token)); break;
case TOK_TYPE_INTEGER: printf("%d\n", tok_state_read_int(s, token)); break;
case TOK_TYPE_FLOAT: printf("%f\n", tok_state_read_float(s, token)); break;
}
}
token_prev = token;
}
tok_state_destroy(s);
}
这将打印：
Token Meaning
101 if
16 (
500 Integer Constant #1 1
8 +
500 Integer Constant #2 1
19 ==
500 Integer Constant #3 4
17 )
104 then
503 Identifier #1 print
502 String Constant #1 hi!
7 ;
105 end
正如其他答案所说，正则表达式本身没有任何问题。但不仅如此，正则表达式是字符级语法的自然表示。
所有主要（以及许多（大多数？）次要语言）都使用正则表达式来定义不同输入标记的外观，至少作为设计语言的形式主义。
但正则表达式库提供的某些技巧确实可能会降低性能。这是因为很多事情，比如反向引用，必须由功能较弱的自动机来实现，而不是更 纯 的正则表达式。
正则表达式（没有反向引用等花哨的东西）可以转换为有限自动机或状态机，并且可以用更简单的方式实现（即 更快）控制功能。
至少，为了提高效率，您应该尝试预编译您的语言定义表达式并使用编译后的匹配器对象，而不是每次都动态构造一个新的匹配器对象。如果你的正则表达式库不提供这个，也许是时候去图书馆购物，或者阅读自动机理论。
复杂语言 ("has expressions with (...) or compound nested statements like do-while, if-then-else") 的任何解释器或编译器都需要您构建解析器来提取代码的（通常是递归的）结构。
你在这里得到了很多答案"regular expressions are good for tokens"。是的，在许多 class 内置的编译器和解释器中，人们编写正则表达式来描述单个标记（标识符、关键字、数字和字符串常量、注释）的形状，并将它们交给词法分析器生成器（如 Flex 或many others) 将这些组合成一个高效的有限状态机。这是可行的，因为令牌的 "syntax" 几乎总是非常简单。这种非常简单意味着您可以自己编写一个令牌词法分析器，并为中小型语言产生实际结果。 （在某些时候（例如，COBOL）语言的庞大规模开始让你不知所措，如果你想保持理智，很难避免使用词法分析器生成器）。
没有讨论的是真实的解析，假设我们已经以某种方式构建了令牌，发现结构。对令牌使用正则表达式不是解析。正则表达式不能用于解析；他们无法识别嵌套结构，而这是那些 "sophisticated" 构造所需要的。 不熟悉解析的人会反复犯这个错误。
如果你想成功，你需要学习如何构建解析器。
对于复杂的语言，有解析器生成器（YACC、JavaCC、many others），类似于词法分析器生成器，它将采用 BNF 并为您生成解析器。如果你想用这样的工具编写一个编译器，你通常将 解析器操作 附加到语法规则识别点，通常是为以后的处理构建树。
您也可以 hand-code a parser for modest size languages. 这是一组相互递归的过程，每个语法规则一个，用于分析代码（使用递归来处理嵌套结构）。您还可以将解析操作附加到过程。由于这些过程识别语法结构，这实际上与您在使用解析器生成器时应用的技巧本质上是相同的。可以简单地扩展此方案以处理令牌的 "parsing"(lexing)。如果你完全沿着这条路走下去，那么任何地方都没有正则表达式。
可以通过在语法规则识别中执行解释器操作来构建解释器 places/in 手动编码的递归解析过程。它不会 运行 很快，因为它会不断地重新解析源代码。
不如建一个(abstract) syntax tree (AST) representing the program, and then build and interpreter that crawls the AST to execute it。 AST 是通过将树构建操作附加为解析器操作来构建的。
如果你想生成字节码，那么你有一个classic 代码生成问题。这些通常最好通过构建 AST 来解决，几乎像解释器一样遍历 AST，并吐出旨在在每个点实现解释器目的的字节代码。您可以通过在解析器操作中生成字节代码来构建即时代码生成器。以这种方式生成 "good" 代码比较困难，因为代码生成器看不到足够的上下文来很好地处理特殊情况。
您可以摸索着完成所有这些。最好的方法是获得一本编译器书籍，或者使用编译器 class。那么这一切都会清楚很多。当然，如果您摸索着解决这个问题，您将更好地理解人们用来执行此操作的编译器的种类。 （Google 我关于 "Life After Parsing" 的文章）。