算术表达式和赋值的 LL1 文法

Question

我想为算术方程式和变量赋值设计一个 LL1 文法。我从这个语法开始：

我有一个无歧义的算术表达式语法：

E → T E’
E’ →  | + E
T → id T’
T’ →  | * T

但是，我不确定如何将变量赋值合并到 E 作品中。

我之前的尝试是：

    stmt -> assignment SEMI | RETURN stmt_prime 
   | LBRACE stmt_list RBRACE 
   | IF LPAREN assignment RPAREN stmt stmt_prime_prime 
   | FOR LPAREN assignment SEMI assignment SEMI assignment RPAREN stmt | 
    stmt_prime -> SEMI | -> assignment SEMI
    stmt_prime_prime -> NOELSE 
    | ELSE stmt
    assignment -> ID typ ASSIGN expr | expr  
    expr -> TE* 
    E* -> + TE* | -TE* | epsilon
    T -> FT*
    T* -> * FT* | / FT* | epsilon
    F -> (E) | int_literal | TRUE | FALSE

Answer 1

assignment -> ID ASSIGN expr | expr

（我忽略了 typ 部分，因为我认为它是偶然到达那里的）

这里的问题是 ID ASSIGN expr 和 expr 都可以以 ID 开头（或者如果 T 包含 ID 至少他们可以一个选项，我认为这是意图），所以这不是 LL(1)。不过它是 LL(2)，所以如果您对此没问题，您可以在解析器的 if 条件中添加一个 andalso next_token = ASSIGN 并完成它。

如果你确实需要它是 LL(1)，恐怕你必须调整你的解析器允许的语言（也就是说，没有完全匹配的 LL(1) 语法与您当前语法相同的语言）。一种简单的解决方法是在赋值之前简单地添加一个关键字，如 SET，尽管这很丑陋。

另一种选择是允许任意表达式作为 = 的左操作数，使您的赋值规则：

assignment -> exp (ASSIGN exp)?

这是 LL(1)。这样做的缺点是它允许很多无意义的代码，例如 1+2 := 42，但您可以在语法之外修复它。也就是说，您用于解析赋值的代码可以简单地调用 parse_exp 然后，如果下一个标记是 ASSIGN 并且 parse_exp 返回的表达式不仅仅是一个标识符，则引发一个错误赋值的左侧必须是标识符。

算术表达式和赋值的 LL1 文法

LL1 grammar for arithmetic expressions and assignments

grammar

parsing

ocaml

ambiguous-grammar