C语言 如何处理相同的符号用于两个东西柠檬解析器

Question

我正在开发一个领域特定的语言。部分语言完全类似于C表达式解析语义，如优先级和符号。

我正在使用Lemon解析器。我遇到了一个问题，同一个令牌被用于两个不同的东西，我无法在词法分析器中分辨出它们的区别。& (&)符号用于"位与"one_answers"的地址"。

一开始我认为这是一个微不足道的问题，直到我意识到它们没有相同的结合律。

如何赋予同一个令牌两个不同的联想性?我应该只使用AMP(如&)并使地址和位规则使用AMP，或者我应该使用不同的令牌(如addressof和BITWISE_AND)。如果我确实使用了单独的符号，我怎么能从词法分析器中知道是哪个符号呢(如果它本身不是解析器，它就无法知道!)

如果你要显式地写出规则，为每个"优先级"级别使用不同的非终结符，那么你根本不需要声明优先级，也不应该这样做。

Lemon，像所有的yacc衍生物一样，使用优先级声明来消除歧义语法中的歧义。这里提到的特殊的歧义语法是:

expression: expression '+' expression
          | expression '*' expression
          | '&' expression
          | ... etc, etc.

在这种情况下，每个选项都会导致shift-reduce冲突。如果您的解析器生成器没有优先规则，或者您想要精确，则必须将其编写为无歧义语法(这就是您所做的):

term: ID | NUMBER | '(' expression ')' ;
postfix_expr:        term | term '[' expression '] | ... ;
unary_expr:          postfix_expr | '&' unary_expr | '*' unary_expr | ... ;
multiplicative_expr: unary_expr | multiplicative_expr '*' postfix_expr | ... ;
additive_expr:       multiplicative_expr | additive_expr '+' multiplicative_expr | ... ;
...
assignment_expr:     conditional_expr | unary_expr '=' assignment_expr | ...; 
expression:          assignment_expr ;
[1]

注意，无二义性语法甚至显示了左结合(上面的乘法和加法)和右结合(赋值，尽管它有点奇怪，参见下面)。所以真的没有歧义。

现在，优先级声明(%left, %right等)仅用于消除歧义。如果没有歧义，则忽略声明。解析器生成器甚至不检查它们是否反映了语法。(事实上，许多语法不能用这种优先关系来表示。)

因此，如果语法是明确的，那么包含优先级声明是一个非常糟糕的主意。他们可能是完全错误的，并误导任何阅读语法的人。更改它们不会影响语言的解析方式，这可能会误导任何想要编辑语法的人。

至少有一些问题，是使用具有优先规则的模糊语法更好，还是使用无模糊语法更好。在C类语言的情况下，其语法不能用简单的优先级列表表示，可能最好使用无二义性语法。然而，明确的语法有更多的状态，可能会使解析稍微慢一些，除非解析器生成器能够优化掉单元约简(上述语法中的所有第一种备选方案，其中每个表达式类型可能只是前一个表达式类型，而不会影响AST;这些结果中的每一个都需要减少，尽管它主要是无操作的，并且许多解析器生成器将插入一些代码。

C不能简单地表示为优先关系的原因正是赋值操作符。考虑:

a = 4 + b = c + 4;

这不能解析，因为在assignment-expression中，赋值操作符只能在左侧应用于unary-expression。这并没有反映+和=之间可能的数字优先级。[2]

如果+的优先级高于=，表达式将解析为:

a = ((4 + b) = (c + 4));

，如果+优先级较低，则解析为

(a = 4) + (b = (c + 4));

---

[1]我刚刚意识到我遗漏了cast_expression，但是我不能被强制转换把它放回去;你懂的)

后来我意识到在解引用(*)和乘法(*)之间也有同样的歧义。

Lemon提供了一种为规则分配优先级的方法，在句点后的方括号中使用关联性声明中使用的名称(%left/right/nonassoc)。

我还没有验证这是否正确工作，但我认为你可以这样做(注意结束附近方括号中的东西):

.
.
.
%left COMMA.
%right QUESTION ASSIGN
    ADD_ASSIGN SUB_ASSIGN MUL_ASSIGN DIV_ASSIGN MOD_ASSIGN
    LSH_ASSIGN RSH_ASSIGN AND_ASSIGN XOR_ASSIGN OR_ASSIGN.
%left LOGICAL_OR.
%left LOGICAL_AND.
%left BITWISE_OR.
%left BITWISE_XOR.
%left BITWISE_AND.
%left EQ NE.
%left LT LE GT GE.
%left LSHIFT RSHIFT.
%left PLUS MINUS.
%left TIMES DIVIDE MOD.
//%left MEMBER_INDIRECT ->* .*
%right INCREMENT DECREMENT CALL INDEX DOT INDIRECT ADDRESSOF DEREFERENCE.
.
.
.
multiplicative_expr ::= cast_expr.
multiplicative_expr(A) ::= multiplicative_expr(B) STAR cast_expr(C). [TIMES]
    { A = Node_2_Op(Op_Mul, B, C); }
.
.
.
unary_expr(A) ::= STAR unary_expr(B). [DEREFERENCE]
    { A = Node_1_Op(Op_Dereference, B); }