regex - Grammar LL(1) Dangling else and common left prefix -

i believe reads familiar dangling else ambiguity. therefore skip explanation. found on compilers book(the dragon book) not ambiguous grammar represents if , else. here is.

stmt->matched_stmt | open_stmt matched_stmt->if exp matched_stmt else matched_stmt | other open_stmt->if exp stmt | if exp matched_stmt else open_stmt 

the problems is:

open_stmt->if exp stmt | if exp matched_stmt else open_stmt

in order make grammar work on ll(1) grammar, need eliminate left common prefix, , in case left common prefix is:

if exp then

when try factory again become ambiguous, tried.

stmt->matched_stmt | open_stmt matched_stmt->if exp matched_stmt else matched_stmt | other open_stmt->if exp theno' o'->stmt | matched_stmt else open_stmt 

which ambiguous, can me make not ambigous , no common left prefix? thank much

i don't believe possible write ll(1) grammar handle dangling else, although trivial write recursive descent parser so.

in recursive descent parser, when you've done parsing first statement after expression, if see else continue production. otherwise, you've finished parsing if statement. in other words, parse else clauses greedily.

but algorithm cannot expressed cfg, , i've assumed impossible write unambiguous ll(1) cfg handles dangling elses, because when reach beginning of s1 in

if e s1 ... 

you still don't know production part of. in fact, don't know until reach end of s1, late make ll(k) decision, no matter how big k is.

however, explanation has lot of hand-waving, , i've never found satisfying. gratified pick battered copy of dragon book (1986 edition) , read, on page 192 ("ll(1) grammars" in section 4.4, "top-down grammars") grammar 4.13 (the if-then-optional-else grammar) "has no ll(1) grammar @ all".

the following paragraph ends sound advice: "if lr parser generator… available, 1 can of benefits of predictive parsing , operator precedence automatically." marginal note (from 1986, guess) reads "so why did study whole chapter????"; today, i'd inclined more generous authors of dragon book not point of suggesting use parser generator not @ least powerful lalr(1) parser generator.