词法分析器和语法分析器的职责

5
我目前正在实现一个简单编程语言的词法分析器。到目前为止,我可以正确地对标识符、赋值符号和整数文字进行标记化;通常,空格是不重要的。
对于输入 foo = 42,识别出三个标记:
  1. foo (标识符)
  2. = (符号)
  3. 42 (整数文字)
到目前为止还不错。但是,请考虑输入 foo = 42bar,由于(显著的)缺少 42bar 之间的空格,这是无效的。我的词法分析器错误地识别出以下标记:
  1. foo (标识符)
  2. = (符号)
  3. 42 (整数文字)
  4. bar (标识符)
一旦词法分析器看到数字 4,它会继续读取,直到遇到非数字字符。因此,它会消耗 2 并将 42 存储为整数文字标记。由于空格是不重要的,词法分析器会丢弃任何空格(如果有的话),并开始读取下一个标记:它找到了标识符 bar现在,我的问题是:词法分析器是否仍然有责任识别该位置不允许使用标识符?还是该检查属于解析器的职责范畴?
4个回答

5
我认为关于42foo是应该被视为无效数字还是两个标记,目前没有共识。这是一个风格问题,两种用法在众所周知的语言中都很常见。
例如:
$ python -c 'print 42and False'
False

$ lua -e 'print(42and false)'
lua: (command line):1: malformed number near '42a'

$ perl -le 'print 42and 0'
42

# Not an idiosyncracy of tcc; it's defined by the standard
$ tcc -D"and=&&" -run - <<<"main(){return 42and 0;}"
stdin:1: error: invalid number

# gcc has better error messages
$ gcc -D"and=&&" -x c - <<<"main(){return 42and 0;}" && ./a.out
<stdin>: In function ‘main’:
<stdin>:1:15: error: invalid suffix "and" on integer constant
<stdin>:1:21: error: expected ‘;’ before numeric constant

$ ruby -le 'print 42and 1'
42

# And now for something completely different (explained below)
$ awk 'BEGIN{print 42foo + 3}'
423

因此,这两种可能性都很常见。
如果你认为数字和单词之间应该用空格分隔,那么你应该在词法分析器中拒绝它。解析器不能(或不应)知道空格是否分隔了两个令牌。42and的有效性独立于此,代码片段42 + 142+142+ 1应该被解析成相同的结果。(除了Fortress语言。但那是个反常现象。)如果你不介意把数字和单词混在一起,那么只有在它是语法错误时,让解析器拒绝它。
另外,值得一提的是,在C和C ++中,42and最初被视为“预处理器数字”。经过预处理后,需要重新进行词法分析,此时才会产生错误消息。这种奇怪的行为的原因是将两个片段粘贴在一起以生成有效数字是完全合法的。
$ gcc -D"c_(x,y)=x##y" -D"c(x,y)=c_(x,y)"  -x c - <<<"int main(){return c(12E,1F);}"
$ ./a.out; echo $?
120

无论是12E还是1F都不是有效的整数,但用##运算符将它们粘在一起就形成了一个完全合法的浮点数。 ## 运算符仅适用于单个标记,因此12E1F都需要词法分析为单个标记。 c(12E+,1F)是不行的,但c(12E0,1F)却可以。

这也是为什么你应该始终在C中在+运算符周围加上空格的原因:经典的C问题:“0x1E+2的值是多少?”

最后,解释awk代码的原因:

$ awk 'BEGIN{print 42foo + 3}'
423

这段代码在awk中被解析为BEGIN{print 42 foo + 3},然后会被视为写成了BEGIN{print (42)(foo + 3);}。在awk中,字符串连接没有运算符,并且其结合性比任何算术运算符都要低。因此,通常建议在涉及连接的表达式中使用显式括号,除非它们非常简单。(另外,如果将未定义的变量用于算术运算,则假定其值为0,如果用作字符串,则假定其值为""。)


+1,非常详细的答案。我也喜欢实际世界的例子。 - Marius Schulz

4

我不同意其他答案。这应该由词法分析器完成。如果数字后面的字符不是空格或特殊字符,则您处于非法标记的中间,具体来说是不以字母开头的标识符。

否则,只需单独返回45和'bar',让解析器将其视为语法错误处理。


这也是我所担心的问题。虽然我并不是词法分析器/语法分析器生成方面的专家,但是让词法分析器接受这个似乎并不太合适。 - Marius Schulz
我实际上误读了描述,尽管“无效”字样很醒目。你是对的,在解析器之前它会失败。 - johncip

1

是的,像这样的上下文检查应该放在解析器中。

此外,您说foo = 42bar是无效的。从词法分析器的角度来看,它并不是无效的。您的词法分析器识别的4个标记可能是正确的(您没有发布标记定义)。

foo = 42bar在您的语言中可能是有效或无效的语句。


好的,那听起来很合理。我的描述可能有误导性:该语句在语言中无效,但我的词法分析器仍然可以识别标记。我只是想确保在那个时候词法分析器不标记无效标记是可以的。 - Marius Schulz
它们并不是无效的令牌-无效的是这个特定的令牌组合语法-因此解析器会标记(当你有传统的词法/语法分析器架构时)。 - 500 - Internal Server Error
1
除非42bar是语言中的合法标记,例如标识符,否则它应该在词法分析阶段失败。 - user207421

0

编辑:我刚意识到这实际上是您的语言中无效的标记。所以,是的,在那一点上它会失败,因为您没有匹配它的规则。否则,它会是什么,InvalidTokenToken?

但是,假设它是一个有效的标记。假设您编写了一个词法分析器规则,说id = <number>是可以的……那么您对于id = <number> + <number> - <number>以及所有导致这种组合的各种组合要怎么办呢?词法分析器将如何为其中任何一个生成AST?这就是解析器的作用。

您是否使用解析器组合框架?我问这个问题是因为有时候在这些框架中,解析器和词法分析器规则之间的区别开始变得模糊,特别是因为您可能没有明确的语法。但是,您正在解析的语言仍然具有语法,而什么算作解析器规则是语法的每个产生式。在最“底层”,如果您有描述单个终端的规则,比如“数字是一个或多个数字”,那么这就是词法分析器用于的唯一原因——原因是它可以加速解析器并简化其实现。


我正在为教育目的构建一个手写的词法分析器,但当我实现解析器时,我可能会选择使用框架;我还不确定,这主要是为了学习。你的回答为我澄清了一些事情,+1! - Marius Schulz
我刚意识到自己犯了一个错误,因此重写了一些内容。实际上,你的词法分析器看起来将是一个正则表达式列表,每个表达式都有一个与之关联的标记类型编号。对于每组空格之间的字符,你依次尝试每个正则表达式,当匹配成功时,返回带有相应标记类型的字符范围。如果没有匹配成功,则失败。 - johncip

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接