Re: Why context-free?

# Wouldn't it be possible to combine the advantages of an LL grammar with
# the power of two-level grammars? As I understand it (if I do at all) a
# VWG can be viewed as a finite specification of an infinite CFG. So I
# would assume, given a string to parse, you would generate as much of the
# CFG as is necessary to parse the string.


In a vW grammar, you can have a protonotion which encodes different
trees at the same time. If this happens the parser cannot exploit a
large order structure to the attributed parse tree it is created, and
would be hopelessly inefficient.


I don't know a simple or straightforward to explain it, but a given vW
grammar might be regarded as similar to attribute grammar with a
skeleton of context free grammar and metanotions attached that act as
attribute variables. Instead of attribute assignments, you want to use
a more generalised unification (assign or verify existing value).


NEST :: EMPTY; NEST LAYER.
LAYER :: new; LAYER DEF.
DEF :: define TAG.


program : LAYER series defining LAYER.
NEST series defining LAYER :
where NEST defines TAG, reference token, TAG token.
NEST series defining LAYER :
begin token, NEST LAYER1 series defining LAYER1, end token.
NEST LAYER0 series defining LAYER define TAG:
unless LAYER0 defines TAG, reference token, TAG token.


WHETHER NEST LAYER define TAG1 defines TAG:
where (TAG1) is (TAG), WHETHER true;
unless (TAG1) is (TAG), WHETHER NEST LAYER defines TAG.
WHETHER new defines TAG: WHETHER false.
WHETHER NEST LAYER new defines TAG: WHETHER NEST LAYER defines TAG.


Now let '=' represent unification, '!=' anti-unification', and '<'...'>'
mark off a structure. Then rewrite the grammar as


program :
T1 series defining LAYER,
T1 = <LAYER>.
NEST series defining LAYER :
where NEST defines TAG, reference token, TAG token.
NEST series defining LAYER :
begin token,
T2 series defining LAYER1,
end token,
T2 = <NEST LAYER1>.
T3 series defining T4:
T3 = <NEST LAYER0>,
T4 = <LAYER T5>,
T5 = <define TAG>,
unless T6 defines TAG, reference token, TAG token,
T6 = <LAYER0>.


where T7 defines TAG:
T7 = <NEST T8>,
T8 = <LAYER T9>,
T9 = <define TAG1>,
TAG1 = TAG, where true;
T7 = <NEST T8>,
T8 = <LAYER T9>,
T9 = <define TAG1>,
TAG1 != TAG, where T11 defines TAG,
T11 = <NEST LAYER>.
where T13 defines TAG:
T12 = <T13>,
T13 = <new>,
where false.
where NEST LAYER new defines TAG:
T14 = <NEST T15>,
T15 = <LAYER T16>,
T16 = <new>,
where NEST LAYER defines TAG,
T17 = <NEST LAYER>.


unless T7 defines TAG:
T7 = <NEST T8>,
T8 = <LAYER T9>,
T9 = <define TAG1>,
TAG1 = TAG, unless true;
T7 = <NEST T8>,
T8 = <LAYER T9>,
T9 = <define TAG1>,
TAG1 != TAG, unless T11 defines TAG,
T11 = <NEST LAYER>.
unless T13 defines TAG:
T12 = <T13>,
T13 = <new>,
unless false.
unless NEST LAYER new defines TAG:
T14 = <NEST T15>,
T15 = <LAYER T16>,
T16 = <new>,
unless NEST LAYER defines TAG,
T17 = <NEST LAYER>.


# Is there anything that prevents adding a requirement that the
# generated grammar be LL? And how much would this restriction "cost"?
# Would a restricted VWG (LLVWG?) be less powerful than a full VWG?


Once you got 'metanotion-grammar' (not exactly the classic
attribute-grammar), the CF subgrammar are just a bunch of rules you
peel off and feed into your parser generator, LL(k), LR(k), whatever.


--
SM Ryan http://www.rawbw.com/~wyrmwif/
Who's leading this mob?

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