将C-语法转换为LL（1）

我目前正在为C-编译一个编译器。我目前正在研究解析器，出于某种原因，我似乎无法解决EXPRESSION生产中第一次碰撞（终端ID）的问题。下面，是我现在语法的一个子集，是否有人能指出我如何解决冲突（或转换为等价的LL（1）可解析语法）的正确方向。将C-语法转换为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

来源

2016-10-04 jay

尝试删除尽可能多的方法，以保留（子）文法的形状并保留问题。（第一步，扔掉其余的语法，专注于你向我们展示的内容）。当你不能删除任何东西而不会使问题消失时，盯着剩下的东西;通常你会看到如何改变剩下的语法来避免这个问题。然后再添加一切。如果在这一点上你不能弄明白，向我们展示精简语法作为你的问题的扩展，并告诉你什么是你认为的问题。你会得到更多的建议。 –

C不借给自己很好地LL（1）语法分析，所以你正在尝试做的可能是相当难以实现，甚至可能不能够为全面的语法。

但手头的问题，顶级生产

EXPRESSION -> id VAR eq EXPRESSION | SIMPLEEXPRESSION

很容易地看到，id可以是另类的开始，所以一个LL（1）语法分析器不会知道哪一种选择选择。

一个解决方案迫在眉睫的问题是将EXPRESSION生产分成两个选择，一个是始终以id终端开始，一个从来不：

EXPRESSION  -> EXPRESSION_id | EXPRESSION_non_id

对于id替代方案，我们会所需要的id终端前面，然后创建遵循作品的id -only版本：

EXPRESSION_id  -> id (VAR eq EXPRESSION | SIMPLEEXPRESSION_id)

同样，对于t他非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

你可以对其他冲突进行类似的转换，但是由此产生的语法可能变得相当笨拙。

来源

2016-10-05 12:58:43

将C-语法转换为LL（1）

回答

相关问题