词法分析器和解析器通信

Question

大多数词法分析器和解析器相关的资源都展示了它们之间使用流进行通信的方式（或者我这样理解）。解析器通过调用函数 getNextToken() 来请求下一个标记，然后词法分析器通过返回下一个标记来响应它。我们是不是应该把它们看作是同一程序中互动的两个对象，还是说它们是通过流互动的两个独立程序？

另外，我一直没明白为什么不选择串行方法，即词法分析器运行到提供的源的末尾，然后解析器才使用词法分析器的输出进行解析。确切地说，如果词法分析器只有在解析器请求下一个标记时才读取下一个词素，那么错误将如何处理？特别是如果错误发生在文件的末尾，解析器所做的所有计算可能会因错误而被浪费（假设一个没有任何错误处理能力的基本解析器）。最近的输出是否被缓存？

- rajatkhanduja

Answer 1

我的回答仅针对Flex-Bison（或Lex-Yacc）编译模型。我对其他模型了解不多。

我认为词法分析器/语法分析器组合是同一程序中两个协作的模块。 当您使用Flex与Bison时，您会发现后者调用前者提供的yylex()函数（yylex()相当于您问题中的getNextToken()函数）。因此，将它们视为单个程序中协作的单元比将它们视为两个不同的程序更有意义。此外，如果词法分析器和语法分析器是两个不同的程序，您将不得不处理进程间通信、共享内存和相关问题，这会进一步复杂化任务。

回答您的第二个问题： 我可以想到一个重要问题：如果语法分析器在词法分析器完成读取所有输入后才开始工作，则即使是中等大小的程序也会产生巨大的内存使用量，因为您必须为每个标记在内存中存储数据结构(考虑像 , 和 = 这样的标记占据多个字节的内存，您很快就会明白为什么它不具有可伸缩性)。

至于错误处理：如果词法分析器无法将输入与任何正则表达式匹配，那么yylex()应使用以下flex规则向语法分析器返回-1：

.               { return -1; }

(Note the period in the first column, which can match any input symbol except "\n".)

(NOTE: This rule should be the last one in your Flex file as the priority of a rule is determined by its order in the file. Flex matches a token using the first possible rule.)

If the lexer returns -1, it indicates a tokenization error. The Bison parser handles it automatically by calling yyerror(char*) (which ideally should be defined by you). If there's a parsing error in the input, the parser calls yyerror(char*) again.

If you want to display the erroneous piece of code when an error occurs, you need to have a way to access the related source code given the defective token. This approach won't work unless you store associated source code with each token while tokenizing, making the compiler memory-intensive.

- Vicky Chijwani

Answer 2

大多数关于词法分析器和解析器的资源都是用流(stream)进行通信的(至少我是这样理解的)。但我看过的没有一个是这样的。它们依靠词法分析器是一个被解析器调用的单个方法。

- user207421