shift/reduce 冲突及如何解决
shift/reduce conlfict and how to solve
我的教授分配给 me.We 的项目有问题
Goal
::= (Function|Statement)* <EOF>
Function
::= "def" Identifier "(" Argument? ")" ":" Statement
Argument
::= Identifier ("=" Value )? ( "," Identifier ("=" Value )?)*
Statement
::= tab* "if" Comparison ":" Statement
|tab* "while" Comparison ":" Statement
|tab* "for" Identifier "in" Identifier ":" Statement
|tab* "return" Expression
|tab* "print" Expression ("," Expression)*
|tab* Identifier ( "=" | "-=" | "/=" ) Expression
|tab* Identifier "[" Expression "]" "=" Expression
|tab* Function Call
Expression
::= Expression ( "+" | "-" | "*" | "/" ) Expression
| ( "++" | "--" ) Expression
| Expression( "++" | "--" )
| Identifier "[" Expression "]"
| Function Call
| Value
| Identifier
| "(" Expression ")"
| "["Value ( "," Value)*"]"
Comparison
::= Expression ( ">" | "<" | "!=" | "==") Expression
| "true"
| "false"
Function Call
::= Identifier "(" Arglist? ")"
Arglist
::= Expression ( "," Expression )*
Value
::= Number | "<STRING_LITERAL>"|'<STRING_LITERAL>'
Number
::= <INTEGER_LITERAL>
Identifier
::= <IDENTIFIER>
<STRING_LITERAL> = A word that can contain letter(capitals or non capital) and white spaces
<INTEGER_LITERAL> = An integer number
<IDENTIFIER> = Name of a variable
而且我们必须用词法和句法实现一个语法文件 analysis.I 已经实现了大部分行,但我在实现其余部分时遇到了问题,因为我得到 shift/reduce conflict.My代码是这个
Helpers
digit = ['0' .. '9'];
letter = ['a' .. 'z']|['A' .. 'Z'];
cr = 13;
lf = 10;
all = [0..127];
eol = lf | cr | cr lf ;
not_eol = [all - [cr + lf]];
Tokens
tab = 9;
plus = '+';
dplus = '++';
minus = '-';
dminus = '--';
mult = '*';
div = '/';
eq = '=';
minus_eq = '-=';
div_eq = '/=';
exclam = '!';
l_br = '[';
r_br = ']';
l_par = '(';
r_par = ')';
comma=',';
def = 'def';
if = 'if';
elif = 'elif';
else = 'else';
for = 'for';
in = 'in';
while = 'while';
print = 'print';
return = 'return';
less = '<';
great = '>';
not_eq = '!=';
log_eq = '==';
true = 'true';
semi = ':';
false = 'false';
quote = '"';
blank = (' ' | lf | cr);
line_comment = '#' not_eol* eol;
number = digit+;
id = letter (letter | digit)*;
string = ('"'not_eol* '"' | ''' not_eol* ''');
Ignored Tokens
blank, line_comment;
Productions
programme = commands*;
commands ={stat} statement|
{expr}expression;
function = {function} def id l_par argument? r_par semi statement;
argument = {argument} id arg1? arg2*;
arg1 = {arg1} eq value;
arg2 = {arg2} comma id arg1?;
statement = {if}tab* if comparison semi statement |
{while}tab* while comparison semi statement |
{for}tab* for [id1]:id in [id2]:id semi statement |
{return}tab* return expression|
{print}tab* print expression |
{assign}tab* id eq expression |
{reduce_by}tab* id minus_eq expression |
{divide_by}tab* id div_eq expression |
{array_element_assing}tab* id l_br [ex2]:expression r_br eq [ex32]:expression;
comparison = {true} true|
{false} false|
{lessc} [lpar]:expression less [rpar]:expression|
{greatc}[lpar]:expression great [rpar]:expression|
{equal} [lpar]:expression log_eq [rpar]:expression|
{not_equal} [lpar]:expression not_eq [rpar]:expression;
expression = {multiplication} multiplication |
{addition} expression plus multiplication |
{subtraction} expression minus multiplication |
{array}id l_br expression r_br;
multiplication = {something} something |
{multiplication} multiplication mult something |
{division} multiplication div something |
{postfix} suffix;
suffix = {dplus} dplus something |
{dminus} dminus something ;
value = {number} number |
{string} string;
something ={identifier}id|
{numb}number|
{par} l_par expression r_par;
如果没有 shift/reduce 冲突,我不能包含的行是
在声明中
|tab* Function Call
在表达式中
|Expression( "++" | "--" )
| Function Call
| "["Value ( "," Value)*"]"
和行
Function Call
::= Identifier "(" Arglist? ")"
Arglist
::= Expression ( "," Expression )*
我只发布了生产部分而不是所有内容,因为问题出在 there.I 希望得到一些帮助,了解如何在没有 shift/reduce conflict.I 的情况下将这些行添加到我的语法中现在几天来解决这个问题,看来我已经尝试 everything.Thanks 提前寻求您的帮助。
您的语法允许 expression
成为 command
(您混淆地称为 commands
)。给你的语法没有。
由于没有命令分隔符,您的语法允许连续的表达式。然而,这是模棱两可的。 a+b
是单个表达式,还是两个表达式 a
和 +b
? a(b)
呢?函数调用,或表达式 a
后跟表达式 (b)
?等等。
您需要重新考虑什么是命令的决定。
顺便说一下,something
对于非终结符来说是个糟糕的名字,我觉得你把冒号称为 (:
) semi
很让人困惑;分号实际上是 ;
,这是我假设 semi
所指的。
我的教授分配给 me.We 的项目有问题
Goal
::= (Function|Statement)* <EOF>
Function
::= "def" Identifier "(" Argument? ")" ":" Statement
Argument
::= Identifier ("=" Value )? ( "," Identifier ("=" Value )?)*
Statement
::= tab* "if" Comparison ":" Statement
|tab* "while" Comparison ":" Statement
|tab* "for" Identifier "in" Identifier ":" Statement
|tab* "return" Expression
|tab* "print" Expression ("," Expression)*
|tab* Identifier ( "=" | "-=" | "/=" ) Expression
|tab* Identifier "[" Expression "]" "=" Expression
|tab* Function Call
Expression
::= Expression ( "+" | "-" | "*" | "/" ) Expression
| ( "++" | "--" ) Expression
| Expression( "++" | "--" )
| Identifier "[" Expression "]"
| Function Call
| Value
| Identifier
| "(" Expression ")"
| "["Value ( "," Value)*"]"
Comparison
::= Expression ( ">" | "<" | "!=" | "==") Expression
| "true"
| "false"
Function Call
::= Identifier "(" Arglist? ")"
Arglist
::= Expression ( "," Expression )*
Value
::= Number | "<STRING_LITERAL>"|'<STRING_LITERAL>'
Number
::= <INTEGER_LITERAL>
Identifier
::= <IDENTIFIER>
<STRING_LITERAL> = A word that can contain letter(capitals or non capital) and white spaces
<INTEGER_LITERAL> = An integer number
<IDENTIFIER> = Name of a variable
而且我们必须用词法和句法实现一个语法文件 analysis.I 已经实现了大部分行,但我在实现其余部分时遇到了问题,因为我得到 shift/reduce conflict.My代码是这个
Helpers
digit = ['0' .. '9'];
letter = ['a' .. 'z']|['A' .. 'Z'];
cr = 13;
lf = 10;
all = [0..127];
eol = lf | cr | cr lf ;
not_eol = [all - [cr + lf]];
Tokens
tab = 9;
plus = '+';
dplus = '++';
minus = '-';
dminus = '--';
mult = '*';
div = '/';
eq = '=';
minus_eq = '-=';
div_eq = '/=';
exclam = '!';
l_br = '[';
r_br = ']';
l_par = '(';
r_par = ')';
comma=',';
def = 'def';
if = 'if';
elif = 'elif';
else = 'else';
for = 'for';
in = 'in';
while = 'while';
print = 'print';
return = 'return';
less = '<';
great = '>';
not_eq = '!=';
log_eq = '==';
true = 'true';
semi = ':';
false = 'false';
quote = '"';
blank = (' ' | lf | cr);
line_comment = '#' not_eol* eol;
number = digit+;
id = letter (letter | digit)*;
string = ('"'not_eol* '"' | ''' not_eol* ''');
Ignored Tokens
blank, line_comment;
Productions
programme = commands*;
commands ={stat} statement|
{expr}expression;
function = {function} def id l_par argument? r_par semi statement;
argument = {argument} id arg1? arg2*;
arg1 = {arg1} eq value;
arg2 = {arg2} comma id arg1?;
statement = {if}tab* if comparison semi statement |
{while}tab* while comparison semi statement |
{for}tab* for [id1]:id in [id2]:id semi statement |
{return}tab* return expression|
{print}tab* print expression |
{assign}tab* id eq expression |
{reduce_by}tab* id minus_eq expression |
{divide_by}tab* id div_eq expression |
{array_element_assing}tab* id l_br [ex2]:expression r_br eq [ex32]:expression;
comparison = {true} true|
{false} false|
{lessc} [lpar]:expression less [rpar]:expression|
{greatc}[lpar]:expression great [rpar]:expression|
{equal} [lpar]:expression log_eq [rpar]:expression|
{not_equal} [lpar]:expression not_eq [rpar]:expression;
expression = {multiplication} multiplication |
{addition} expression plus multiplication |
{subtraction} expression minus multiplication |
{array}id l_br expression r_br;
multiplication = {something} something |
{multiplication} multiplication mult something |
{division} multiplication div something |
{postfix} suffix;
suffix = {dplus} dplus something |
{dminus} dminus something ;
value = {number} number |
{string} string;
something ={identifier}id|
{numb}number|
{par} l_par expression r_par;
如果没有 shift/reduce 冲突,我不能包含的行是
在声明中
|tab* Function Call
在表达式中
|Expression( "++" | "--" )
| Function Call
| "["Value ( "," Value)*"]"
和行
Function Call
::= Identifier "(" Arglist? ")"
Arglist
::= Expression ( "," Expression )*
我只发布了生产部分而不是所有内容,因为问题出在 there.I 希望得到一些帮助,了解如何在没有 shift/reduce conflict.I 的情况下将这些行添加到我的语法中现在几天来解决这个问题,看来我已经尝试 everything.Thanks 提前寻求您的帮助。
您的语法允许 expression
成为 command
(您混淆地称为 commands
)。给你的语法没有。
由于没有命令分隔符,您的语法允许连续的表达式。然而,这是模棱两可的。 a+b
是单个表达式,还是两个表达式 a
和 +b
? a(b)
呢?函数调用,或表达式 a
后跟表达式 (b)
?等等。
您需要重新考虑什么是命令的决定。
顺便说一下,something
对于非终结符来说是个糟糕的名字,我觉得你把冒号称为 (:
) semi
很让人困惑;分号实际上是 ;
,这是我假设 semi
所指的。