Programmeeropgave: BNF-regels toepassen

AExpr   <- Term (AddOp Term)*

Term    <- Factor (MultOp Factor)*

Factor  <- UFactor / AddOp Factor

UFactor <- Primary ("^" Factor)?

Primary <- "n" / "(" AExpr ")"

AddOp   <- "+" / "-"

MultOp  <- "*" / "/"

Quoted from Dan the Man on zondag 06 februari 2022

Anders zou de volgende string worden geaccepteerd: "+-+-++---+--++n".

Niet zo moelijk om met de hand een recursive-descent parsertje voor te schrijven, dus.

local GGP = require "GGP-2"



local Bargain =

  { aanbieding = 'som prijs | som "+" aanbieding'

  , som        = 'getal | som "+" getal'

  , getal      = 'cijfer | getal cijfer'

  , cijfer     = '"0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"'

  , prijs      = '"gratis"'

  }



GGP.translate(Bargain)

GGP:start("2+1gratis", aanbieding)

GGP:publish()

2 unique structures match "2+1gratis" after 81146 calls generating 14748 expressions (max. depth was 38):



  {{{{{2}}}+{{1}}}{gratis}}

  {{{{2}}}+{{{{1}}}{gratis}}}



or reduced:



  {2+1}gratis

  2+{1gratis}

local GGP = require "GGP-2"



local Conditional =

  { cond_stmt = 'if_stmt | if_stmt "else." stmt'

  , if_stmt   = '"if.Cond.then." stmt'

  , stmt      = '"Stmt." | cond_stmt'

  }



GGP.translate(Conditional)

GGP:start("if.Cond.then.if.Cond.then.Stmt.else.Stmt.", cond_stmt)

GGP:publish()

2 unique structures match "if.Cond.then.if.Cond.then.Stmt.else.Stmt." after 99 calls generating 24 expressions (max. depth was 16):



  {{if.Cond.then.{{{if.Cond.then.{Stmt.}}else.{Stmt.}}}}}

  {{if.Cond.then.{{{if.Cond.then.{Stmt.}}}}}else.{Stmt.}}



or reduced:



  if.Cond.then.{{if.Cond.then.Stmt.}else.Stmt.}

  {if.Cond.then.{if.Cond.then.Stmt.}}else.Stmt.

2+2*1 = <aexpr>

          ├───<aexpr>

          │     └───<term>

          │           └───"2"

          ├───<addop>

          │     └───"+"

          └───<term>

                │───<term>

                │     └───"2"

                │───<multop>

                │     └───"*"

                └───<factor>

                      └───<ufactor>

                            └───<primary>

                                  └───<number>

                                        └───<digit>

                                              └───"1"

local GGP  = require "GGP-2"

local load = loadstring or load  -- to be compatible with Lua 5.1 and 5.2+



local expression = arg[1]

local startrule  = arg[2]



if expression and startrule then

  local L =

    assert(load("return {" .. (io.stdin:read "*a"):gsub("\n", ", \n") .. "}"))()

  GGP.translate(L)

  GGP:start(expression, assert(load("return " .. startrule))())

  GGP:publish()

else

  io.stderr:write [[

Two arguments required:

  (1) a test expression

  (2) a non-terminal to start with



]]

end

==> luaJIT test-BNF-8.lua "2+2*1" aexpr < arithmetic.bnf



==> luaJIT test-BNF-8.lua "2+1gratis" aanbieding < bargain.bnf



==> luaJIT test-BNF-8.lua "if Cond then if Cond then Stmt else Stmt " cond_stmt < conditional.bnf

cond_stmt = 'if_stmt | if_stmt "else " stmt'

if_stmt   = '"if Cond then " stmt'

stmt      = '"Stmt " | cond_stmt'

aexpr  = 'term ADDING' 

term   = '"n"'

ADDING = 'addop term ADDING | " "'

addop  = '"+" | "-"'

2+2*1 = <aexpr>

          ├───<aexpr>

          │     └───<term>

          │           └───<factor>

          │                 └───<ufactor>

          │                       └───<primary>

          │                             └───<number>

          │                                   └───<digit>

          │                                         └───"2"

          ├───<addop>

          │     └───"+"

          └───<term>

                │───<term>

                │     └───<factor>

                │           └───<ufactor>

                │                 └───<primary>

                │                       └───<number>

                │                             └───<digit>

                │                                   └───"2"

                │───<multop>

                │     └───"*"

                └───<factor>

                      └───<ufactor>

                            └───<primary>

                                  └───<number>

                                        └───<digit>

                                              └───"1"

• Het verbod op lege strings in de BNF is nu opgeheven, zij het op straffe van verminderde zekerheid dat in geval van lege strings altijd alle oplossingen worden gevonden. Je kunt deze vergroten door het proces meer tijd te gunnen, maar 100% betrouwbaar wordt het uiteindelijk nooit.
  
• Interessanter is de aanzienlijk verbeterde performance. Waar GGP.lua er niet in slaagde binnen 24 uur de expressie −n−(n+n)*−n^−n^n te analyseren, heeft GGP-3.lua er minder dan een kwart seconde voor nodig. De lat om dit te overtreffen ligt nu wel flink hoger.
  

LuaJIT test-BNF-A.lua "a+b=c+d=e+f" expr5 < assignment.bnfx   ⟹   a+{b={c+{d={e+f}}}}

LuaJIT test-BNF-A.lua "a+b=c+d=e+f" expr6 < assignment.bnfx   ⟹   {a+b}={{c+d}={e+f}}

LuaJIT test-BNF-A.lua "a+b=c+d=e+f" expr4 < assignment.bnfx   ⟹   a+{b={c+{d={e+f}}}}   [1e van 5 oplossingen]

LuaJIT test-BNF-A.lua "a+b+c=d+e=f" expr4 < assignment.bnfx   ⟹   {a+b}+{c={d+{e=f}}}   [1e van 2 oplossingen]

LuaJIT test-BNF-A.lua "a=b+c+d+e=f" expr4 < assignment.bnfx   ⟹   a={{{b+c}+d}+{e=f}}   [1e van 4 oplossingen]

LuaJIT test-BNF-A.lua "a=b+c+d=e=f" expr4 < assignment.bnfx   ⟹   a={{b+c}+{d={e=f}}}   [1e van 3 oplossingen]

expr10 = 'term10 | expr10 "+" term10'

term10 = 'var | number | "(" expr10 ")" | var "=" expr10'

var    = '"a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "m" | "n" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"'

number = 'digit | digit number'

digit  = '"0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"'

expr11  = 'var "=" expr11 | aexpr11'

aexpr11 = 'term11 | aexpr11 "+" term11'

term11  = 'var | number | "(" expr11 ")"'

...