3

我正在开发一种特定领域的语言。语言的一部分与 C 表达式完全一样，解析判据和符号等语义。

我正在使用柠檬解析器。我遇到了一个问题，即同一个令牌被用于两种不同的事情，我无法分辨词法分析器中的区别。& 符号用于“按位与”和“地址”。

起初我认为这是一个微不足道的问题，直到我意识到它们没有相同的关联性。

如何给同一个令牌两个不同的关联性？我应该只使用 AMP（如与符）并使 addressof 和按位和规则使用 AMP，还是应该使用不同的令牌（例如 ADDRESSOF 和 BITWISE_AND）。如果我确实使用了单独的符号，我应该如何从词法分析器中知道哪个符号（如果不是解析器本身就无法知道！）。

4

2 回答 2

3

如果你要明确地写出规则，为每个“优先级”级别使用不同的非终端，那么你根本不需要声明优先级，你不应该这样做。

Lemon 与所有 yacc 派生词一样，使用优先级声明来消除歧义语法中的歧义。所指的特定模棱两可的语法是这样的：

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

在这种情况下，每一个备选方案都会导致班次减少冲突。如果您的解析器生成器没有优先规则，或者您想要精确，则必须将其编写为明确的语法（这就是您所做的）：

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-like 语言，其语法不能用简单的优先级列表表示，最好只使用明确的语法。然而，明确的文法有更多的状态并且可能使解析稍微慢一些，除非解析器生成器能够优化掉单位减少（上述文法中的所有第一个替代方案，其中每个表达式类型可能只是前一个不影响 AST 的表达式类型；这些产生式中的每一个都需要减少，尽管它主要是无操作的，并且许多解析器生成器会插入一些代码。）

原因C不能简单地表示为优先关系，恰恰是赋值运算符。考虑：

a = 4 + b = c + 4;

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

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

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

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

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

[1] 我刚刚意识到我遗漏了 cast_expression 但我无法将其重新放入；你明白了）

[2] 描述已修复。

于 2012-12-28T23:56:48.620 回答
0

后来我意识到我在取消引用（*）和乘法（*）之间也有同样的歧义。

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); }
于 2012-12-28T22:36:53.130 回答