Sat Jul 02, 2022 6:02 am
Login Register Lost Password? Contact Us

Please Note: The HPCC Systems forums are moving to Stack Overflow. We invite you to post your questions on Stack Overflow utilizing the tag hpcc-ecl ( This legacy forum will be active and monitored during our transition to Stack Overflow but will become read only beginning September 1, 2022.

Why is this grammar ambiguous?

Questions around writing code and queries

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


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;

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?

Posts: 444
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.
Parsing "a" "a" "a".... should that match
["a" [ "a"] "a"]
["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)

  TOKEN<0> tok0  := 'a';
  TOKEN<1> tok1  := 'b';
  TOKEN<2> EOF ;
  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
   EndOfToken: []
   Token DFA numStates="3" numTransitions="2"   Skip DFA numStates="2" numTransitions="48"
   [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]} []
   [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: 
   [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
Posts: 444
Joined: Sat Oct 01, 2011 7:26 pm

Return to Programming

Who is online

Users browsing this forum: No registered users and 1 guest