将 C- 语法转换为 LL(1)

Question

我目前正在构建一个 C 语言编译器。我目前正在研究解析器，由于某种原因，我似乎无法解决源自 EXPRESSION 生成的第一组冲突（终端 id）。下面是我现在拥有的语法的一个子集，有人可以指出我如何解决冲突的正确方向（或转换为等效的 LL(1) 可解析语法）。

EXPRESSION ->   id VAR eq EXPRESSION |  SIMPLEEXPRESSION 

VAR ->  lbracket EXPRESSION rbracket |  empty

SIMPLEEXPRESSION -> ADDITIVEEXPRESSION FADDITIVEEXPRESSION 

FADDITIVEEXPRESSION ->  RELOP ADDITIVEEXPRESSION |  empty

RELOP ->    ltoreq |    lt |    gt |    gtoreq |    doubleeq |  noteq 

ADDITIVEEXPRESSION ->   TERM ADDITIVEEXPRESSION1 

ADDITIVEEXPRESSION1 ->  ADDOP TERM ADDITIVEEXPRESSION1 |    empty

ADDOP ->    plus |  minus 

TERM -> FACTOR TERM1 

TERM1 ->    MULOP FACTOR TERM1 |    empty

MULOP ->    times | divide 

FACTOR ->   lparen EXPRESSION rparen |  id FACTOR1 |    num 

FACTOR1 ->  a | b

Answer 1

C 不太适合 LL(1) 解析，因此您在这里尝试做的事情可能很难实现，甚至对于完整的语法来说可能是不可能的。

但是为了眼前的问题，为了顶级的制作

EXPRESSION ->   id VAR eq EXPRESSION |  SIMPLEEXPRESSION 

很容易看出

id

可以是任一替代方案的开始，因此 LL(1) 解析器将不知道选择哪个替代方案。

解决眼前问题的一个解决方案是将

EXPRESSION

的产生分为两种替代方案，一种总是以

id

终端开始，另一种则从不这样做：

EXPRESSION        ->   EXPRESSION_id |  EXPRESSION_non_id

对于

id

替代方案，我们需要预先使用

id

终端，然后创建以下产品的仅

id

版本：

EXPRESSION_id     ->   id (VAR eq EXPRESSION |  SIMPLEEXPRESSION_id) 

同样，对于非

id

方面，我们将创建以下产品的非

id

版本：

EXPRESSION_non_id ->   SIMPLEEXPRESSION_non_id

完成语法所需的子产生式如下所示：

SIMPLEEXPRESSION_id -> ADDITIVEEXPRESSION_id FADDITIVEEXPRESSION 
ADDITIVEEXPRESSION_id ->   TERM_id ADDITIVEEXPRESSION1 
TERM_id -> FACTOR_id TERM1
FACTOR_id ->   FACTOR1

SIMPLEEXPRESSION_non_id -> ADDITIVEEXPRESSION_non_id FADDITIVEEXPRESSION 
ADDITIVEEXPRESSION_non_id ->   TERM_non_id ADDITIVEEXPRESSION1
TERM_non_id -> FACTOR_non_id TERM1
FACTOR_non_id ->   lparen EXPRESSION rparen |  num

您可以对其他冲突进行类似的转换，但生成的语法可能会变得非常难以处理。

Answer 2

为了保持理智，通常最好将表达式解析器从 LL 切换到 Pratt。 Pratt 表达式解析是一件简单的事情 - 整个解析器或多或少都适合一屏高级代码（Python、TS、Haskell、Rust 等）。

有关 LL 和 Pratt 解析之间切换的更多信息，请参阅 matklad 的弹性 LL 解析教程。

请注意，Pratt 和 Shunting Yard 是相同的算法，只是描述方式不同。