----------------------------------------------------------------------
--- Knud van Eeden --- 18 April 2008 - 10:14 pm ----------------------

BBCBASIC: Windows: Compiler: Syntax: Parser: LL: How to apply a top down parsing using a table? Example: ( 1 + 1 ) [LL parser / rewrite rule] [<Research>]

---

Steps: Overview:

 1. -E.g. create the following program:

--- cut here: begin --------------------------------------------------

      expression$ = "(1+1)"
      REM expression$ = "(((1+1)+1)+1)"
      REM expression$ = "((1+1)+1)"
      :
      *SPOOL "c:\ddd.txt"
      :
      stack$ = ""
      :
      result$ = ""
      :
      DIM table$( 3, 6 )
      :
      FOR rowI% = 1 TO 3
        FOR columnI% = 1 TO 6
          READ s$
          table$( rowI%, columnI% ) = s$
        NEXT columnI%
      NEXT rowI%
      :
      DATA " ", "(", ")", "1", "+", "$"
      DATA "S", "2", "-", "1", "-", "-"
      DATA "F", "-", "-", "3", "-", "-"
      :
      DIM rewriteRule$( 3, 2 )
      :
      FOR rowI% = 1 TO 3
        FOR columnI% = 1 TO 2
          READ s$
          rewriteRule$( rowI%, columnI% ) = s$
        NEXT columnI%
      NEXT rowI%
      :
      DATA "S", "F"
      DATA "S", "(S+F)"
      DATA "F", "1"
      :
      nonTerminal$ = ""
      :
      FOR rowI% = 1 TO 3
        nonTerminal$ = nonTerminal$ + table$( rowI%, 1 )
      NEXT rowI%
      :
      terminal$ = ""
      :
      FOR columnI% = 1 TO 6
        terminal$ = terminal$ + table$( 1, columnI% )
      NEXT columnI%
      :
      PRINT "expression"; " "; "="; " "; expression$
      PRINT
      :
      PRINT "stack"; " "; "="; " "; stack$
      PRINT
      :
      PRINT "result"; " "; "="; " "; result$
      PRINT
      :
      PRINT "table"
      FOR rowI% = 1 TO 3
        FOR columnI% = 1 TO 6
          PRINT; table$( rowI%, columnI% ); " ";
        NEXT columnI%
        PRINT
      NEXT rowI%
      :
      PRINT
      :
      PRINT "rewrite rules"
      FOR rowI% = 1 TO 3
        FOR columnI% = 1 TO 2
          PRINT; rewriteRule$( rowI%, columnI% ); " ";
        NEXT columnI%
        PRINT
      NEXT rowI%
      :
      PRINT
      :
      PRINT "non terminals"; " "; "="; " "; nonTerminal$
      :
      PRINT
      :
      PRINT "terminals"; " "; "="; " "; terminal$
      :
      expression$ = expression$ + "$"
      :
      stack$ = "$" + stack$
      :
      stack$ = "S" + stack$
      :
      I% = 0 + 2
      REPEAT
        :
        I% = I% + 1
        :
        token$ = LEFT$( expression$, 1 )
        :
        topStack$ = LEFT$( stack$, 1 )
        :
        nonTerminalTopStackB% = ( INSTR( nonTerminal$, topStack$ ) <> 0 )
        :
        terminalExpressionB% = ( INSTR( terminal$, token$ ) <> 0 )
        :
        terminalTopStackB% = ( INSTR( terminal$, topStack$ ) <> 0 )
        :
        IF terminalExpressionB% AND nonTerminalTopStackB% THEN
          rowI% = INSTR( nonTerminal$, topStack$ )

          columnI% = INSTR( terminal$, token$ )
          rewriteRuleRow$ = table$( rowI%, columnI% )
          rewriteRuleRowI% = VAL( rewriteRuleRow$ )
          rewriteRuleRightHand$ = rewriteRule$( rewriteRuleRowI%, 2 )
          stack$ = RIGHT$( stack$, LEN( stack$ ) - LEN( topStack$ ) )
          stack$ = rewriteRuleRightHand$ + stack$
          result$ = result$ + rewriteRuleRow$
        ELSE IF terminalExpressionB% AND terminalTopStackB% THEN
            IF NOT ( token$ = topStack$ ) THEN
              PRINT "error: token '"; token$; "' unequal to top stack '"; topStack$; "'. Thus not a valid expression"
              STOP
            ENDIF
            :
            expression$ = RIGHT$( expression$, LEN( expression$ ) - LEN( token$ ) )
            stack$ = RIGHT$( stack$, LEN( stack$ ) - LEN( topStack$ ) )
          ELSE
            PRINT "error 1"
          ENDIF
        ENDIF
        :
        PRINT

        PRINT "step = "; I%
        PRINT "token = "; token$
        PRINT "top stack = "; topStack$
        PRINT "expression = "; expression$
        PRINT "stack = "; stack$
        PRINT "result = "; result$
        PRINT "---"
      UNTIL ( expression$ = "$" )
      :
      PRINT "this expression parse is"; " ";
      IF stack$ = "$" THEN
        PRINT "valid"
      ELSE
        PRINT "invalid"
      ENDIF
      :
      *SPOOL
      :
      END

--- cut here: end ----------------------------------------------------

 2. -Run the program

 3. -That will show a screen output similar to the following:

--- cut here: begin --------------------------------------------------
expression = (1+1)

stack =

result =

table
  ( ) 1 + $
S 2 - 1 - -
F - - 3 - -

rewrite rules
S F
S (S+F)
F 1

non terminals =  SF

terminals =  ()1+$

step = 3
token = (
top stack = S
expression = (1+1)$
stack = (S+F)$
result = 2
---

step = 4
token = (
top stack = (
expression = 1+1)$
stack = S+F)$
result = 2
---

step = 5
token = 1
top stack = S
expression = 1+1)$
stack = F+F)$
result = 21
---

step = 6
token = 1
top stack = F
expression = 1+1)$
stack = 1+F)$
result = 213
---

step = 7
token = 1
top stack = 1
expression = +1)$
stack = +F)$
result = 213
---

step = 8
token = +
top stack = +
expression = 1)$
stack = F)$
result = 213
---

step = 9
token = 1
top stack = F
expression = 1)$
stack = 1)$
result = 2133
---

step = 10
token = 1
top stack = 1
expression = )$
stack = )$
result = 2133
---

step = 11
token = )
top stack = )
expression = $
stack = $
result = 2133
---
this expression parse is valid

--- cut here: end ----------------------------------------------------

===

Book: see also:



===

Help: see also:



===

Internet: see also:



===

Image: see also:



===

Screencast: see also:



===

Video: see also:





---



----------------------------------------------------------------------