RE: Recursive Descent vs. LALR

Chris F. Clark said:


> It is worth noting that the intersection of two cfgs need not be a
> cfg, but the intersection of two csgs is a csg. Predicates
> (mentioned above) allow one to write grammatically grammars that
> are the intersection of context free grammars, which allows
> predicated parsers (either LL or LR) to parse context-sensitive
> languages.


That turns out to be a nifty observation in theory, so I thought I
would demonstrate it in practice.


grammar AnBnCn
{
S ::=


($a(X S.x<*>) $b(Y S.y<*>))<a b=anbn> $c(Z<S.x!=S.z> S.z<*>)<b
c=bncn>;


anbn ::= S.x [anbn] S.y;
bncn ::= S.y [bncn] S.z;


X ::= $S.x<-("(" '[a-z][a-z]+' ")");


Y ::= $S.y<-("(" '[a-z][a-z]+' ")");


Z ::= $S.z<-("(" '[a-z][a-z]+' ")");
}; // grammar AnBnCn


The above $-grammar accepts strings in the form:


(a)^n(b)^n(c)^n where |a| > 1, |b| > 1, |c| > 1, and a != c


Thus:


(cat)(cat)(dog)(dog)(mouse)(mouse)


but not


(cat)(cat)(dog)(mouse)(mouse)


and not


(cat)(cat)(mouse)(mouse)(cat)(cat)


How it actually goes about its magic is found in the back referencing
and predicates.


Here's an English-ed version of the first production, S:


$a(X S.x<*>))


"Match an X followed by zero to many of whatever X matched, and place
the result into a."


  $b(Y S.y<*>))<a b=anbn>


"Match a Y followed by zero to many of whatever Y matched, and place
the result into b. Concatenate a and b, and parse the resulting string
with anbn. Fail if a+b is not accepted by anbn."


$c(Z<S.x!=S.z> S.z<*>)<b c=bncn>


"Match a Z. Fail if whatever matched X is equal to whatever matched Z,
otherwise, match zero to many of whatever matched Z, and place the
final result into c. Concatenate b and c, and parse the resulting
string with bncn. Fail if b+c is not accepted by bncn."


The cumulative result of the predicate intersections and the back
referencing is a grammar that accepts the language described.


> BTW, adaptive grammars are equivalent in power to TMs.


Right. Strictly speaking, the notations in the above grammar are
sufficient for Turing Power (give or take a notation), but I leave
that as an exercise for the reader.


--
Quinn Tyler Jackson

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