Is equivalent conflict detection simplification in LL(1) ?
Borneq
borucki.andrzej at gmail.com
Sat Nov 2 16:12:36 UTC 2024
LL parser table.
For LL(1), the following rules apply for deciding whether there
is a conflict:
for each pair of different productions of the same non-terminal
symbol (let's call it A):
1. strings beginning with the same terminal symbol cannot be
output.
2. two productions cannot simultaneously allow the derivation of
an empty (epsilon) string
3. if an empty string can be output from one production, no
string starting with any terminal symbol belonging to FOLLOW(A)
can be output from the other production
This is caused by the fact that the terminal symbol is used to
select the production; while the first point is clear, points 2
and 3 result from the fact that when outputting the entire
string, when the string generated by the productions ends, there
is a return to the overriding (in the dynamic sense) production
that generates further symbols, you can imagine it as a return to
the procedure calling the current procedure. Point 2 follows from
the fact that otherwise, for both selection paths, we would have
tokens with FOLLOW(A) (in addition to those specific only to
those productions)
It follows from conditions 1 and 2 that the FIRST sets should be
disjoint for both productions. The third condition is equivalent
to the requirement that if an epsilon belongs to the FIRST of one
production then the FIRST sets of the other and FOLLOW(A) are
disjoint.
I have a question: if there is an epsilon, can tokens from
FOLLOW(A) be added to the set of productions and then only
compare the sets with each other, is this equivalent or so
enriched
More information about the Digitalmars-d-learn
mailing list