regular LALR parsers (Simon Huntington)
Fri, 13 Aug 1993 16:31:51 GMT

          From comp.compilers

Related articles
regular LALR parsers (1993-08-13)
Re: regular LALR parsers (1993-08-16)
Re: regular LALR parsers (1993-08-30)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Simon Huntington)
Keywords: parse, LALR, question
Organization: SoftWare Interrupt Developments
Date: Fri, 13 Aug 1993 16:31:51 GMT

How does an LALR parser with regular expressions (eg. *, +, []) handle the
attribute stack? Obviously, the attributes on the stack depend on the number
of iterations of constructs such as *, +.

I thought it may be possible to collect attributes into lists for +, * at the
end of each iteration on a shift action. eg.

X -> (a b)* c

When the parser reaches the end of the ()* construct (ie. after shifting b),
it can either shift c (and leave the * construct), or shift a (and enter the
construct again). So, I thought, if the action causes the construct to be
entered again, gather the attributes for the last iteration into another list
and place that on some other stack. If the action causes the construct to be
left, the attributes of all iterations are made into another list from the
contents of the other stack. eg.

the attribute of (a b) is a list, type:

a_b_iteration** all_ab_iterations;

struct a_b_iteration
A* a's attribute
B* b's attribute

I've also worked out how to handle optional constructs etc.., but the problem
is that the attribute stack manipulation depends on a shift action and there
may be other shifts on the same symbol that don't require the actions. eg.

Y -> (a b)+ a

when the parser reaches the end of the + construct, it can shift a and
leave the construct (stack manipulation required), otherwise it can enter
the iteration again (stack manipulation required) - both actions are
different and both can't be executed.

So, what do I do? Avoid grammars that cause the problem or is there an easier
way where I won't get shift action conflicts? Would it be possible to group
attributes into lists when the rule is finally reduced.

Ideas or comments appreciated.
Simon Huntington
Software Interrupt Developments. Leeds, UK.

Post a followup to this message

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