去除模糊
我有以下野牛语法(如更复杂的语法的一部分):去除模糊
classDeclaration : CLASS ID EXTENDS ID LBRACE variableDeclarationList methodDeclarationList RBRACE
;
variableDeclarationList : variableDeclarationList variableDeclaration
| /* empty */
;
variableDeclaration : type ID SEMICOLON
;
type : NATTYPE | ID
;
methodDeclarationList : methodDeclarationList methodDeclaration
| /* empty */
;
methodDeclaration : type ID LPAREN parameterDeclarationList RPAREN variableExpressionBlock
;
这是为了描述的类声明,其看起来像这样:
class foo extends object
{
nat number;
nat divide(nat aNumber)
{
0;
}
}
或这样的:
class foo extends object
{
nat divide(nat aNumber)
{
0;
}
}
或本:
class foo extends object
{
}
问题是,有歧义其中变量声明端和方法声明开始(2移/减少冲突)。例如,方法声明看起来像一个变量声明,直到它看到括号。
我怎么可以重写此语法来消除这种不确定性?
澄清:类体可以是空的,唯一的限制是,如果有任何变量声明之前方法声明来临。
另一种方法是甚至不使用空规则,而是使用多个选项,一个使用非终结符和一个没有。
classDeclaration : CLASS ID EXTENDS ID LBRACE RBRACE
| CLASS ID EXTENDS ID LBRACE methodDeclarationList RBRACE
| CLASS ID EXTENDS ID LBRACE variableDeclarationList RBRACE
| CLASS ID EXTENDS ID LBRACE variableDeclarationList methodDeclarationList RBRACE
;
variableDeclarationList : variableDeclaration
| variableDeclarationList variableDeclaration
;
variableDeclaration : type ID SEMICOLON
;
type : NATTYPE
| ID
;
methodDeclarationList : methodDeclaration
| methodDeclarationList methodDeclaration
;
methodDeclaration : type ID LPAREN RPAREN variableExpressionBlock
| type ID LPAREN parameterList RPAREN variableExpressionBlock
;
我不熟悉的野牛,但你有没有试图使一个规则的规则都在共同的前缀? “类型ID”以变量和方法模式存在。
所以,如果你有说:
typedId : type ID
;
然后
variableDeclaration : typedId SEMICOLON
;
methodDeclaration : typedId LPAREN parameterDeclarationList RPAREN variableExpressionBlock
;
这样的变化规律和方法规则不会在直到被看作共同的前缀已经推,而下代币应该是明确的。
我已经很多年没有与这样的事情打我希望这有助于。
此略作修改语法的工作原理:
%token CLASS EXTENDS ID LBRACE RBRACE SEMICOLON NATTYPE LPAREN RPAREN DIGIT COMMA
%%
classDeclaration : CLASS ID EXTENDS ID LBRACE declarationList RBRACE
;
declarationList : /* Empty */
| declarationList declaration
;
declaration : variableDeclaration
| methodDeclaration
;
variableDeclaration : parameterDeclaration SEMICOLON
;
type : NATTYPE | ID
;
methodDeclaration : parameterDeclaration LPAREN parameterDeclarationList RPAREN
variableExpressionBlock
;
variableExpressionBlock : LBRACE DIGIT RBRACE
;
parameterDeclarationList : /* empty */
| parameterDeclarationList COMMA parameterDeclaration
;
parameterDeclaration : type ID
;
你可能想在非终端“parameterDeclaration”重命名为类似“singleVariableDeclaration”,但通过避免连续有两个可能是空的规则(原'variableDeclarationList'和'methodDeclarationList',你可以避免含糊不清
这确实允许在类的declarationList中与变量交错的方法,如果由于某种原因这是不可接受的,那么考虑做一个语义错误而不是一个语法错误,如果它必须是一个语法错误,那么有人将不得不做一些思考;我投票让你做这个想法。
如果你坚持至少一个方法声明,那么语法是明确的:
methodDeclarationList : methodDeclarationList methodDeclaration
| methodDeclaration /* empty */
;
如果你试图用变量声明列表相同,语法仍然有两个S/R冲突。
一个不被完全忽略的可能性是使用Bison功能%expect 2
来指示预计会出现2次移位/减少冲突。
%expect 2
%token CLASS EXTENDS ID LBRACE RBRACE SEMICOLON NATTYPE LPAREN RPAREN DIGIT COMMA
%%
classDeclaration : CLASS ID EXTENDS ID LBRACE variableDeclarationList methodDeclarationList RBRACE
;
variableDeclarationList : variableDeclarationList variableDeclaration
| /* empty */
;
variableDeclaration : singleVariableDeclaration SEMICOLON
;
type : NATTYPE | ID
;
methodDeclarationList : methodDeclarationList methodDeclaration
| /* empty */
;
methodDeclaration : singleVariableDeclaration LPAREN parameterDeclarationList RPAREN variableExpressionBlock
;
variableExpressionBlock : LBRACE DIGIT RBRACE
;
parameterDeclarationList : /* empty */
| parameterDeclarationList COMMA parameterDeclaration
;
parameterDeclaration : singleVariableDeclaration
;
singleVariableDeclaration : type ID
;
这不是模棱两可,其先行的问题。问题是你需要3个令牌的lookahead(直到下一个声明的SEMICOLON
或LPAREN
),以便解析器找出变量声明列表的结尾,因为它需要在开始解析更多的methodDeclarations之前减少一个空的methodDeclarationList 。
解决这个问题的方法是在方法声明列表的开始,不需要用一个空的减少:
methodDeclarationList : nonEmptyMethodDeclarationList | /*empty */ ;
nonEmptyMethodDeclarationList : nonEmptyMethodDeclarationList methodDeclaration
| methodDeclaration
;
这样,解析器不需要,除非有降低空methodDeclarationList没有任何方法 - 在这种情况下,只需要一个前瞻标记即可看到RBRACE
有趣的理论。尽管如此,野牛仍然有麻烦,仍然有2个转变/减少冲突。 – ladookie
通常,这种左分解仅对基于LL的解析器生成器有用。基于LR的发电机(比如野牛)会自动为你做这件事。 –