Thu Jul 18, 2019 11:50 am
Login Register Lost Password? Contact Us


Why is this grammar ambiguous?

Questions around writing code and queries

Tue Apr 16, 2019 8:41 am Change Time Zone

Hi,

To get my head around the Tomita variant of parsing.
I've generated the very simplest grammar, (where there are lots of examples on the Web).
Just to parse palindromes. So I have:
Code: Select all
TOKEN a := 'a';
TOKEN b := 'b';

attrRec := RECORD
STRING  val;
END;

RULE(attrRec) expr := a  USE(attrRec,expr) a
                    | b  USE(attrRec,expr) b
                    | (a|b) TRANSFORM(attrRec,SELF.val := $1 );

infile := DATASET([{'aba'},{'a'},{'b'},{'ab'}],{ STRING line });

OUTPUT(PARSE(infile,line,expr,{STRING Text := MATCHTEXT},FIRST,WHOLE,PARSE,SKIP([' ','\t']+)));

This all works, but I get this warning:
Code: Select all
Warning:  The PARSE pattern for activity 3 is ambiguous.  This may reduce the efficiency of the PARSE. (15, 8), 4537,

And I can't for the life of me work out why.

Any ideas?

Allan
Allan
 
Posts: 373
Joined: Sat Oct 01, 2011 7:26 pm

Wed May 08, 2019 10:24 am Change Time Zone

OK I've had a reply from Gavin.
It is because it is ambiguous with single token look ahead.
E.g.
Parsing "a" "a" "a".... should that match
["a" [ "a"] "a"]
or
["a" ["a" ["a"
You cannot tell until all the tokens are parsed.
Try adding
#option ('debugNlp', 1);
to the query - it adds a comment to the c++ file describing the grammar.


Example Dump of Grammar in said c++ file:
Code: Select all
Human readable form of the grammar
   
Options:  Match(First)  Scan(Whole)
Matches:
   expr{3}

Features:
Tokens:
  TOKEN<0> tok0  := 'a';
  TOKEN<1> tok1  := 'b';
  TOKEN<2> EOF ;
Rules:
  Rule<3> expr
    CanBeNull(0) First[?] Follow[2 0 1]
    Production<0>: [] CloningTransform := tok0 expr tok0
    Production<1>: [] CloningTransform := tok1 expr tok1
    Production<2>: [] := rule6
  Rule<4> a
    CanBeNull(0) First[?] Follow[]
    Production<3>: [] := tok0
  Rule<5> b
    CanBeNull(0) First[?] Follow[]
    Production<4>: [] := tok1
  Rule<6> rule6
    CanBeNull(0) First[?] Follow[2 0 1]
    Production<5>: [] := tok0
    Production<6>: [] := tok1
  Rule<7> rule7
    CanBeNull(0) First[?] Follow[]
    Production<7>: [] := expr
Lexer:
   EndOfToken: []
   Token DFA numStates="3" numTransitions="2"   Skip DFA numStates="2" numTransitions="48"
States:
   [0] I={[7,0]} [0->1,1->2,3->3,6->4]
   [1] I={[0,1],[5,1]} [0->1,1->2,3->5,6->4]
   [2] I={[1,1],[6,1]} [0->1,1->2,3->6,6->4]
   [3] I={[7,1]} []
   [4] I={[2,1]} []
   [5] I={[0,2]} [0->7]
   [6] I={[1,2]} [1->8]
   [7] I={[0,3]} []
   [8] I={[1,3]} []
Parser:
States:
   Root=0
   [0]      S1   S2         Goto:  3->3 6->4
   [1]      {S1R5}   {S2R5}   R5      Goto:  3->5 6->4
   [2]      {S1R6}   {S2R6}   R6      Goto:  3->6 6->4
   [3]            A      Goto: 
   [4]      R2   R2   R2      Goto: 
   [5]      S7            Goto: 
   [6]         S8         Goto: 
   [7]      R0   R0   R0      Goto: 
   [8]      R1   R1   R1      Goto: 
Productions:
   [0]   rule:3 pop:3
   [1]   rule:3 pop:3
   [2]   rule:3 pop:1
   [3]   rule:4 pop:1
   [4]   rule:5 pop:1
   [5]   rule:6 pop:1
   [6]   rule:6 pop:1
   [7]   rule:7 pop:1
Allan
 
Posts: 373
Joined: Sat Oct 01, 2011 7:26 pm


Return to Programming

Who is online

Users browsing this forum: No registered users and 0 guests