Compilers - Looking for LL(k) C grammar

Author

Looking for LL(k) C grammar

Italo Tasso

2007-11-05, 4:29 am

I am looking for a LL(k) C grammar. Here is my problem:

I am trying to make a recursive descent parser for a simplified
version of C. It doesn't have to be predictive, but it would be good
to have no backup.

I started with the grammar in the K&R book. I removed some left
recursion and did some factorization. I was going bottom up in the
grammar, starting from the "constant" production. The problem is here:

assignment-expression: conditional-expression
| unary-expression assignment-operator assignment-expression
;

conditional-expression has unary-expression in it, so I must factorize it to
make it LL(k). But since there are so many productions between
conditional-expression and unary-expression, I just don't know how to do it.

I found some LL(2) C grammars with google, but they have some inconsistencies
when compared to the grammar in K&R.

I attached the grammar I wrote so far.

Thanks in advance.
exp : assignment_exp exp_sufix
;

exp_sufix : ',' assignment_exp exp_sufix
| empty
;

assignment_exp : unary_exp assignment_operator assignment_exp
| conditional_exp
;

assignment_operator : '=' | '*=' | '/=' | '%=' | '+=' | '-=' | '<<='
| '>>=' | '&=' | '^=' | '|='
;

conditional_exp : logical_or_exp conditional_exp_sufix
;

conditional_exp_sufix : '?' exp ':' conditional_exp
| empty
;

const_exp : conditional_exp
;

logical_or_exp : logical_and_exp logical_or_exp_sufix

logical_or_exp_sufix : '||' logical_and_exp logical_or_exp_sufix
| empty
;

logical_and_exp : inclusive_or_exp logical_and_exp_sufix
;

logical_and_exp_sufix : '&&' inclusive_or_exp logical_and_exp_sufix
| empty
;

inclusive_or_exp : exclusive_or_exp inclusive_or_exp_sufix
;

inclusive_or_exp_sufix : '|' exclusive_or_exp inclusive_or_exp_sufix
| empty
;

exclusive_or_exp : and_exp exclusive_or_exp_sufix
;

exclusive_or_exp_sufix : '^' and_exp exclusive_or_exp_sufix
| empty
;

and_exp : equality_exp and_exp_sufix
;

and_exp_sufix : '&' equality_exp and_exp_sufix
| empty
;

equality_exp : relational_exp equality_exp_sufix

equality_exp_sufix : '==' relational_exp equality_exp_sufix
| '!=' relational_exp equality_exp_sufix
| empty
;

relational_exp : shift_expression relational_exp_sufix

relational_exp_sufix : '<' shift_expression relational_exp_sufix
| '>' shift_expression relational_exp_sufix
| '<=' shift_expression relational_exp_sufix
| '>=' shift_expression relational_exp_sufix
| empty
;

shift_expression : additive_exp shift_expression_sufix
;

shift_expression_sufix : '<<' additive_exp shift_expression_sufix
| '>>' additive_exp shift_expression_sufix
| empty
;

additive_exp : mult_exp additive_exp_sufix
;

additive_exp_sufix : '+' mult_exp additive_exp_sufix
| '-' mult_exp additive_exp_sufix
| empty
;

mult_exp : cast_exp mult_exp_sufix
;

mult_exp_sufix : '*' cast_exp mult_exp_sufix
| '/' cast_exp mult_exp_sufix
| '%' cast_exp mult_exp_sufix
| empty
;

cast_exp : unary_exp
;

unary_exp : postfix_exp
| '++' unary_exp
| '--' unary_exp
| unary_operator cast_exp
;

unary_operator : '&' | '*' | '+' | '-' | '~' | '!'
;

postfix_exp : primary_exp postfix_exp_sufix
;

postfix_exp_sufix : '[' exp ']' postfix_exp_sufix
| '(' ')' postfix_exp_sufix
| '(' argument_exp_list ')' postfix_exp_sufix
| '.' id postfix_exp_sufix
| '->' id postfix_exp_sufix
| '++' postfix_exp_sufix
| '--' postfix_exp_sufix
| empty
;

primary_exp : id
| const
| '(' exp ')'
;

argument_exp_list : assignment_exp argument_exp_list_sufix
;

argument_exp_list_sufix : ',' assignment_exp argument_exp_list_sufix
| empty
;

const : int_const
;

rssh

2007-11-05, 8:13 am

On Nov 3, 1:51 pm, "Italo Tasso" <it...@spwinternet.com.br> wrote:
> I am looking for a LL(k) C grammar. Here is my problem:

Have you seen the C grammars in JavaCC and ANTLR distributions ?

George Neuner

2007-11-06, 7:19 pm

On Sat, 3 Nov 2007 09:51:13 -0200, "Italo Tasso"
<italo@spwinternet.com.br> wrote:

>I am trying to make a recursive descent parser for a simplified
>version of C. It doesn't have to be predictive, but it would be good
>to have no backup.

Recursive descent is predictive by nature.

You can't realistically avoid "backing up" in an RD parser if your
language is LL(k>1), but you can reduce the impact. Unreading a token
or two is very fast ... it's when you have to clean up partial parse
results and undo complex actions like tables updates that backtracking
becomes painful. The best remedy is to implement the parser in a GC'd
language (C and C++ have GC libraries) and code important data
structures in a functional style as much as possible so you can just
abandon the updates if necessary.

>I started with the grammar in the K&R book.

Which is incomplete.

C is fairly complex to parse. Depending on what your subset consists
of, you may be better off just locating an existing grammar written
for your parser tool and pruning the stuff you don't need.

George

Sponsored Links