Need help regarding one LALR(1) parsing

Question

I am trying to parse a context-free language, called Context Free Art. I have created its parser in Javascript using a YACC-like JS LALR(1) parser generator JSCC.

Take the example of following CFA (Context Free Art) code. This code is a valid CFA.

startshape A
rule A { CIRCLE { s 1} }

Notice the A and s in above. s is a command to scale the CIRCLE, but A is just a name of this rule. In the language's grammar I have set s as token SCALE and A comes under token STRING (I have a regular expression to match string and it is at the bottom of of all tokens).

This works fine, but in the below case it breaks.

startshape s
rule s { CIRCLE { s 1} }

This too is a perfectly valid code, but since my parser marks s after rule as SCALE token so it errors out saying that it was expecting STRING.

Now my question is, if there is any way to re-write the production rules of the parser to account for this? The related production rule is:-

rule:
    RULE STRING '{' buncha_replacements '}'    [* rule(%2, 1) *]
    |
    RULE STRING RATIONAL '{' buncha_replacements '}'  [* rule(%2, 1*%3) *]
    ;

One simple solution I can think of is create a copy of above rule with STRING replaced by SCALE, but this is just one of the many similar rules which would need such fixing. Furthermore there are many other terminals which can get matched to STRING. So that means way too many rules!

Just an add-on to above. YACC (or maybe Bison) supports type tokens. So for them if we declare `STRING` as a type token then `s` can be both `SCALE` and `STRING`, solving this problem. Not sure if this can be done in JSCC. — AppleGrew, Jun 23 '11 at 11:00

score 0 · Answer 1 · answered Jun 23 '11 at 13:44

Yes! Finally the solution to my problem has hit me. All I need to do is modify my above production to:-

rule:
    RULE user_string '{' buncha_replacements '}'    [* rule(%2, 1) *]
    |
    RULE user_string RATIONAL '{' buncha_replacements '}'  [* rule(%2, 1*%3) *]
    ;

user_string:
    STRING | SCALE ;

This is a pretty elegant solution compared to what I mentioned in my problem text. If anybody has any better solution then please do comment.

Need help regarding one LALR(1) parsing

1 Answers1