Re: ll(1) and variable assignment...

weltraum@astrocat.de (Chris) wrote:
# hi,
#
# I want to write a recursive descent parser, and wonder if there is a
# LL(1) grammar for "c-style" variable assignement
# (i.e. "id=id=id+id" but not "id=id=id+id=2").
#
# The following grammar is LL(2) I think:
#
# A := ID = A
# A := E
#
# E := T E'
# E':= + T E'
# E':=
#
# T := ID
# T := ( A )


<A> ::= ID = <a-expression>
FIRST: {ID}
<a-expression> ::= ID <a-suffix>
FIRST: {ID}
| (<expression>) <suffix>
FIRST: {"("}
<a-suffix> :: = <a-expression>
FIRST: {"="}
| <suffix>
FIRST: {"+"}
<expression> ::= ID <a-suffix>
FIRST: {ID}
| (<expression>) <suffix>
FIRST: {"("}
<suffix> :: = + <expression>
FIRST: {"+"}
| empty
FIRST: FOLLOWER(A)


The parse tree is going to be a bear to untangle, though.


The only problem is that in C, the thingie before the '=', the l-value, has unbounded
size and can be nested deeply in an embedding-(-) production; potentially you won't
know it's not a l-value until deep inside the parse and shifting any number of tokens.
That means it won't be LL(k) for any k. But if the l-value can be described as something
akin to a regular expression, then it is still LL(k).


--
SM Ryan http://www.rawbw.com/~wyrmwif/
Title does not dictate behaviour.

Return to the comp.compilers page.
Search the comp.compilers archives again.