0

我正在为其编写解析器的语言具有三个与此处相关的结构:由ord表示的运算符,TOK_ORD它将字符表达式转换为整数表达式,以及[ ].,分别用于索引和字段访问,就像在 C 中一样。

这是我的优先规则的摘录:

%right TOK_ORD
%left  PREC_INDEX PREC_MEMBER

我的语法有一个非终结符expr,它代表表达式。这是语法中的一些相关片段(TOK_IDENT是我.l文件中定义的标识符的正则表达式):

expr     : TOK_ORD expr                         { /* semantic actions */ }
         | variable                             { /* semantic actions */ }
         ;
variable : expr '[' expr ']' %prec PREC_INDEX   { /* semantic actions */ }
         | expr '.' TOK_IDENT %prec PREC_MEMBER { /* semantic actions */ }
         ;

以下是野牛输出文件中有关移位/减少冲突的信息:

state 61

42 expr: expr . '=' expr
43     | expr . TOK_EQ expr
44     | expr . TOK_NE expr
45     | expr . TOK_LT expr
46     | expr . TOK_LE expr
47     | expr . TOK_GT expr
48     | expr . TOK_GE expr
49     | expr . '+' expr
50     | expr . '-' expr
51     | expr . '*' expr
52     | expr . '/' expr
53     | expr . '%' expr
57     | TOK_ORD expr .
72 variable: expr . '[' expr ']'
73         | expr . '.' TOK_IDENT

'['  shift, and go to state 92
'.'  shift, and go to state 93

'['       [reduce using rule 57 (expr)]
'.'       [reduce using rule 57 (expr)]
$default  reduce using rule 57 (expr)

州 92 和 93,供参考:

state 92

72 variable: expr '[' . expr ']'

TOK_FALSE      shift, and go to state 14
TOK_TRUE       shift, and go to state 15
TOK_NULL       shift, and go to state 16
TOK_NEW        shift, and go to state 17
TOK_IDENT      shift, and go to state 53
TOK_INTCON     shift, and go to state 19
TOK_CHARCON    shift, and go to state 20
TOK_STRINGCON  shift, and go to state 21
TOK_ORD        shift, and go to state 22
TOK_CHR        shift, and go to state 23
'+'            shift, and go to state 24
'-'            shift, and go to state 25
'!'            shift, and go to state 26
'('            shift, and go to state 29

expr       go to state 125
allocator  go to state 44
call       go to state 45
callargs   go to state 46
variable   go to state 47
constant   go to state 48


state 93

73 variable: expr '.' . TOK_IDENT

我不明白为什么会有移位/减少冲突。我的语法清楚地定义了索引和字段访问的优先级高于ord,但这似乎还不够。

如果您想知道,是的,这是家庭作业,但作业已经上交并评分。我要回过头来尝试修复班次/减少冲突,以便更好地了解发生了什么。

4

1 回答 1

2

通过将产生式(或减少,如果您愿意)的优先级与令牌(前瞻令牌)的优先级进行比较,可以解决移位/归约冲突的优先级。

这个简单的事实有点模糊,因为野牛根据生产中最后一个标记的优先级设置生产的优先级(默认情况下),所以似乎优先级值仅分配给标记,并且优先级比较是在标记优先级之间. 但这并不准确:优先级比较总是在产生式(可能会减少)和令牌(可能会转移)之间进行。

正如野牛手册所说:

...通过将正在考虑的规则的优先级与前瞻令牌的优先级进行比较来解决冲突。如果令牌的优先级更高,则选择转移。如果规则的优先级较高,则选择减少。

variable现在,您使用显式声明定义两个产生式的优先级:

variable : expr '[' expr ']' %prec PREC_INDEX   { /* semantic actions */ }
         | expr '.' TOK_IDENT %prec PREC_MEMBER { /* semantic actions */ }

但是这些产品从不参与移位/减少冲突。当任一variable规则结束时,就没有转移的可能性。可以减少这些产生式的项集没有移位动作。

在包含移位/归约冲突的状态下,冲突是潜在归约之间的冲突:

 expr: TOK_ORD expr

以及涉及前瞻令牌.[. 这些冲突将通过分别比较TOK_ORD归约的优先级与前瞻标记的优先级.和来解决[。如果这些令牌没有声明的优先级,则无法使用优先级机制解决移位/归约冲突。

不过,在这种情况下,我希望在其他状态下会有大量的移位/减少冲突,其中选项是减少二元运算符(例如expr: expr '+' expr)或移动./[以扩展最右边的 expr。因此,如果没有这种移位/减少冲突,则解释会更加复杂,我需要查看更多语法才能理解它。

于 2015-05-20T02:31:24.380 回答