The rules never get cut, understanding why
I am learning to work with YACC and I really cannot figure out some of the mistakes. I would like to know why I am getting this error when I try to generate my parser with a .y file. Here is my .y file, which is a contextual free grammar for the Pascal language:
%%
Program : program ident ';' declaration_opc compound_stmt '.'
;
declaration_opc : var declaration_list
|
;
declaration_list : declaration ';' declaration_list
| declaration ';'
;
declaration : id_list ':' type
;
id_list : ident
| ident ',' id_list
;
type : integer
| BOOLEAN
;
proc_dec : proc_header forward ';'
| proc_header declaration_list compound_stmt
| func_header forward ';'
| func_header declaration_list compound_stmt
;
proc_header : procedure ident parametros ';'
;
func_header : function ident parametros : type
;
parametros : '(' param_list ')'
|
;
param_list : arg
| arg ';' param_list
;
arg : id_list ':' type
| var id_list ':' type
;
compound_stmt : begin statement_list end
;
statement_list : statement ';' statement_list
| statement
;
statement : ident attrib expression
| IF expression then statement
| IF expression then statement ELSE statement
| WHILE expression DO statement
| compound_stmt
| readln ident
| writeln print_list
|
;
print_list : literal print_list2
| expression print_list2
;
print_list2 : ',' print_list
|
;
expression : add_expression relop add_expression
| add_expression
;
relop : lessequal
| '<'
| '>'
| moreequal
| '='
| notequal
;
add_expression : add_expression addop term
;
addop : '+'
| '-'
| or
;
term : term mulop unary_exp
| unary_exp
;
mulop : '*'
| div
| mod
| and
;
unary_exp : not unary_exp
| factor
;
factor : '(' expression ')'
| ident
| num
| TRUE
| FALSE
;
%%
And I always get this:
byaccj: 19 rules never reduced
byaccj: 1 shift/reduce conflict.
What's the possible solution for this? I found other people who had the same errors, but I couldn't find something helpful for my problem. If more information is required, I provide. I also read that the "Rules never decreased" error means that some of the rules from my grammar are never used, but I cannot see this with my rules.
source to share
In your case, the rule proc_dec
never appears on the right side of any other rule, so from the start character ( Program
) will never be reached. Yacc simply tells you that this rule (and all the rules it uses and nothing else) are not available.
In general, you want to use the option -v
to get yacc to create a file y.output
with detailed information about your grammar. This file will tell you about all conflicts and unused rules: what they are and how they came about, and the messages just give you a short description of the problems.
source to share
In this case, you have two main sources of problems. First, you just haven't included procedures in your grammar for the program. You would probably fix it with something like:
Program : program ident ';' declaration_opc procedures compound_stmt '.'
;
procedures: proc_dec
| procedures ';' proc_dec
;
[It's been a while since I wrote any Pascal - casually, I don't remember if you really need a semicolon to separate procedures or not, but if not, it's trivial to remove.]
The second area of concern is that your grammar for is add_expression
always infinitely recursive:
add_expression : add_expression addop term
;
You haven't included anything to stop the recursion from the left side. You probably want something like:
add_expression : add_expression addop term
| term addop term
;
For a type expression, a + b - c
it will match the first alternative as: (a + b) add_expression - addop c termand the second alternative would be used to match only the part a + b
like: a term + addop b term...
source to share
The file is incomplete as there are a number of tokens that have never been defined (e.g. BOOLEAN
) If it were complete, we could have given a better answer.
In general, rules that are not reducible are not (as far as yacc can determine) tied to the initial state through any sequence of steps. Thus, they are debris that you must redo or remove.
Here are a few places where this has been discussed before:
source to share
%% Start: _PROGRAM _ID _SEMI Block
Block: Declarations BlockStatements
Announcements: _VAR _LPAREN VariableDeclarions _SEMI _RPAREN _ADD | ;
VariableDeclarions: _ID _LPAREN _COMMA _ID _RPAREN _MULT _COLON TypeSpec
TypeSpec: _INTEGER | priority _real
BlockStatements: _BEGIN _END Statements | ;
Statements: Task W | ;
W: Statements
Application: Appointment | ;
Purpose: _ID _ASSIGN Expr _SEMI
Expr: term _LPAREN _ADD term _RPAREN _MULT | Term _LPAREN _SUB Term _RPAREN _MULT | The term _LPAREN _MULT | Term _LPAREN _DIV _RPAREN _MULT
Term: _CONST | _LPAREN Expr _RPAREN | _I WOULD
this is my grammar
I am getting error like
2 rules never decrease
can someone help me figure out the problem
source to share