Parse EBNF: Difference between revisions
Added Algol 68
Thundergnat (talk | contribs) (→{{header|Perl 6}}: Updated to work with current specs (repetion operator changed). Also displays syntax tree now) |
(Added Algol 68) |
||
| (19 intermediate revisions by 8 users not shown) | |||
Line 1:
[[Category:Recursion]]
{{clarified-review}}
;Task:
Write a program that can parse a grammar in Extended Backus–Naur Form ('''EBNF'''), and then parse something else according to the grammar.
The program is only required to decide whether or not the something else belongs to the language described by the grammar, but for extra credit, it can output a syntax tree.
See [[Parse EBNF/Tests|the tests]].
<br><br>
=={{header|ALGOL 68}}==
The source of the Algol 68 sample is somewhat largish, so is on a separate page on Rosetta Code here: [[Parse EBNF/ALGOL 68]].
{{out}}
<pre>
Valid EBNF: a/z: 'a' { a = 'a1' ( 'a2' | 'a3' ) { 'a4' } [ 'a5' ] 'a6' ; } 'z'
a: seq
literal "a1"
oneof
seq
literal "a2"
seq
literal "a3"
list
literal "a4"
opt
literal "a5"
literal "a6"
"a1a3a4a4a5a6" is valid according to a
"a1 a2a6" is valid according to a
"a1 a3 a4 a6" is valid according to a
**** Syntax error near "a1 a4 a5 a6"
"a1 a4 a5 a6" is not valid according to a
**** Syntax error near "a5 a5 a6"
"a1 a2 a4 a5 a5 a6" is not valid according to a
**** Unexpected text: "a7" at the end of source
"a1 a2 a4 a5 a6 a7" is not valid according to a
**** Syntax error near "your ad here"
"your ad here" is not valid according to a
Valid EBNF: Arithmetic expressions:
'Arithmetic expressions'
{
expr = term { plus term } .
term = factor { times factor } .
factor = number | '(' expr ')' .
plus = '+' | '-' .
times = '*' | '/' .
number = digit { digit } .
digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' .
}
expr: seq
rule term
list
rule plus
rule term
term: seq
rule factor
list
rule times
rule factor
factor: oneof
seq
rule number
seq
literal "("
rule expr
literal ")"
plus: oneof
seq
literal "+"
seq
literal "-"
times: oneof
seq
literal "*"
seq
literal "/"
number: seq
rule digit
list
rule digit
digit: oneof
seq
literal "0"
seq
literal "1"
seq
literal "2"
seq
literal "3"
seq
literal "4"
seq
literal "5"
seq
literal "6"
seq
literal "7"
seq
literal "8"
seq
literal "9"
"2" is valid according to Arithmetic expressions
"2*3 + 4/23 - 7" is valid according to Arithmetic expressions
"(3 + 4) * 6-2+(4*(4))" is valid according to Arithmetic expressions
**** Syntax error near "-2"
"-2" is not valid according to Arithmetic expressions
**** Unexpected text: "+" at the end of source
"3 +" is not valid according to Arithmetic expressions
**** Syntax error near " 3"
"(4 + 3" is not valid according to Arithmetic expressions
**** Expected "{", not "a"
Invalid EBNF: a = '1';
**** Expected "}", not "(eof)"
Invalid EBNF: { a = '1' ;
**** Expected "=", not "world"
Invalid EBNF: { hello world = '1'; }
**** Rule "bar" not defined
Invalid EBNF: { foo = bar . }
</pre>
=={{header|Go}}==
{{trans|Phix}}
<br>
A more or less faithful translation except that indices are 0-based rather than 1-based and so 1 less than in the Phix results.
<syntaxhighlight lang="go">package main
import (
"fmt"
"strings"
)
// type aliases for Phix types
type object = interface{}
type sequence = []object
var (
src []rune
ch rune
sdx int
token object
isSeq bool
err = false
idents []string
ididx []int
productions []sequence
extras sequence
results = [2]string{"pass", "fail"}
)
func btoi(b bool) int {
if b {
return 1
}
return 0
}
func invalid(msg string) int {
err = true
fmt.Println(msg)
sdx = len(src) // set to eof
return -1
}
func skipSpaces() {
for {
if sdx >= len(src) {
break
}
ch = src[sdx]
if strings.IndexRune(" \t\r\n", ch) == -1 {
break
}
sdx++
}
}
func getToken() {
// Yields a single character token, one of {}()[]|=.;
// or {"terminal",string} or {"ident", string} or -1.
skipSpaces()
if sdx >= len(src) {
token = -1
isSeq = false
return
}
tokstart := sdx
if strings.IndexRune("{}()[]|=.;", ch) >= 0 {
sdx++
token = ch
isSeq = false
} else if ch == '"' || ch == '\'' {
closech := ch
for tokend := sdx + 1; tokend < len(src); tokend++ {
if src[tokend] == closech {
sdx = tokend + 1
token = sequence{"terminal", string(src[tokstart+1 : tokend])}
isSeq = true
return
}
}
token = invalid("no closing quote")
isSeq = false
} else if ch >= 'a' && ch <= 'z' {
// To simplify things for the purposes of this task,
// identifiers are strictly a-z only, not A-Z or 1-9.
for {
sdx++
if sdx >= len(src) {
break
}
ch = src[sdx]
if ch < 'a' || ch > 'z' {
break
}
}
token = sequence{"ident", string(src[tokstart:sdx])}
isSeq = true
} else {
token = invalid("invalid ebnf")
isSeq = false
}
}
func matchToken(ch rune) {
if token != ch {
token = invalid(fmt.Sprintf("invalid ebnf (%c expected)", ch))
isSeq = false
} else {
getToken()
}
}
func addIdent(ident string) int {
k := -1
for i, id := range idents {
if id == ident {
k = i
break
}
}
if k == -1 {
idents = append(idents, ident)
k = len(idents) - 1
ididx = append(ididx, -1)
}
return k
}
func factor() object {
var res object
if isSeq {
t := token.([]object)
if t[0] == "ident" {
idx := addIdent(t[1].(string))
t = append(t, idx)
token = t
}
res = token
getToken()
} else if token == '[' {
getToken()
res = sequence{"optional", expression()}
matchToken(']')
} else if token == '(' {
getToken()
res = expression()
matchToken(')')
} else if token == '{' {
getToken()
res = sequence{"repeat", expression()}
matchToken('}')
} else {
panic("invalid token in factor() function")
}
if s, ok := res.(sequence); ok && len(s) == 1 {
return s[0]
}
return res
}
func term() object {
res := sequence{factor()}
tokens := []object{-1, '|', '.', ';', ')', ']', '}'}
outer:
for {
for _, t := range tokens {
if t == token {
break outer
}
}
res = append(res, factor())
}
if len(res) == 1 {
return res[0]
}
return res
}
func expression() object {
res := sequence{term()}
if token == '|' {
res = sequence{"or", res[0]}
for token == '|' {
getToken()
res = append(res, term())
}
}
if len(res) == 1 {
return res[0]
}
return res
}
func production() object {
// Returns a token or -1; the real result is left in 'productions' etc,
getToken()
if token != '}' {
if token == -1 {
return invalid("invalid ebnf (missing closing })")
}
if !isSeq {
return -1
}
t := token.(sequence)
if t[0] != "ident" {
return -1
}
ident := t[1].(string)
idx := addIdent(ident)
getToken()
matchToken('=')
if token == -1 {
return -1
}
productions = append(productions, sequence{ident, idx, expression()})
ididx[idx] = len(productions) - 1
}
return token
}
func parse(ebnf string) int {
// Returns +1 if ok, -1 if bad.
fmt.Printf("parse:\n%s ===>\n", ebnf)
err = false
src = []rune(ebnf)
sdx = 0
idents = idents[:0]
ididx = ididx[:0]
productions = productions[:0]
extras = extras[:0]
getToken()
if isSeq {
t := token.(sequence)
t[0] = "title"
extras = append(extras, token)
getToken()
}
if token != '{' {
return invalid("invalid ebnf (missing opening {)")
}
for {
token = production()
if token == '}' || token == -1 {
break
}
}
getToken()
if isSeq {
t := token.(sequence)
t[0] = "comment"
extras = append(extras, token)
getToken()
}
if token != -1 {
return invalid("invalid ebnf (missing eof?)")
}
if err {
return -1
}
k := -1
for i, idx := range ididx {
if idx == -1 {
k = i
break
}
}
if k != -1 {
return invalid(fmt.Sprintf("invalid ebnf (undefined:%s)", idents[k]))
}
pprint(productions, "productions")
pprint(idents, "idents")
pprint(ididx, "ididx")
pprint(extras, "extras")
return 1
}
// Adjusts Go's normal printing of slices to look more like Phix output.
func pprint(ob object, header string) {
fmt.Printf("\n%s:\n", header)
pp := fmt.Sprintf("%q", ob)
pp = strings.Replace(pp, "[", "{", -1)
pp = strings.Replace(pp, "]", "}", -1)
pp = strings.Replace(pp, " ", ", ", -1)
for i := 0; i < len(idents); i++ {
xs := fmt.Sprintf(`'\x%02d'`, i)
is := fmt.Sprintf("%d", i)
pp = strings.Replace(pp, xs, is, -1)
}
fmt.Println(pp)
}
// The rules that applies() has to deal with are:
// {factors} - if rule[0] is not string,
// just apply one after the other recursively.
// {"terminal", "a1"} -- literal constants
// {"or", <e1>, <e2>, ...} -- (any) one of n
// {"repeat", <e1>} -- as per "{}" in ebnf
// {"optional", <e1>} -- as per "[]" in ebnf
// {"ident", <name>, idx} -- apply the sub-rule
func applies(rule sequence) bool {
wasSdx := sdx // in case of failure
r1 := rule[0]
if _, ok := r1.(string); !ok {
for i := 0; i < len(rule); i++ {
if !applies(rule[i].(sequence)) {
sdx = wasSdx
return false
}
}
} else if r1 == "terminal" {
skipSpaces()
r2 := []rune(rule[1].(string))
for i := 0; i < len(r2); i++ {
if sdx >= len(src) || src[sdx] != r2[i] {
sdx = wasSdx
return false
}
sdx++
}
} else if r1 == "or" {
for i := 1; i < len(rule); i++ {
if applies(rule[i].(sequence)) {
return true
}
}
sdx = wasSdx
return false
} else if r1 == "repeat" {
for applies(rule[1].(sequence)) {
}
} else if r1 == "optional" {
applies(rule[1].(sequence))
} else if r1 == "ident" {
i := rule[2].(int)
ii := ididx[i]
if !applies(productions[ii][2].(sequence)) {
sdx = wasSdx
return false
}
} else {
panic("invalid rule in applies() function")
}
return true
}
func checkValid(test string) {
src = []rune(test)
sdx = 0
res := applies(productions[0][2].(sequence))
skipSpaces()
if sdx < len(src) {
res = false
}
fmt.Printf("%q, %s\n", test, results[1-btoi(res)])
}
func main() {
ebnfs := []string{
`"a" {
a = "a1" ( "a2" | "a3" ) { "a4" } [ "a5" ] "a6" ;
} "z" `,
`{
expr = term { plus term } .
term = factor { times factor } .
factor = number | '(' expr ')' .
plus = "+" | "-" .
times = "*" | "/" .
number = digit { digit } .
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
}`,
`a = "1"`,
`{ a = "1" ;`,
`{ hello world = "1"; }`,
`{ foo = bar . }`,
}
tests := [][]string{
{
"a1a3a4a4a5a6",
"a1 a2a6",
"a1 a3 a4 a6",
"a1 a4 a5 a6",
"a1 a2 a4 a5 a5 a6",
"a1 a2 a4 a5 a6 a7",
"your ad here",
},
{
"2",
"2*3 + 4/23 - 7",
"(3 + 4) * 6-2+(4*(4))",
"-2",
"3 +",
"(4 + 3",
},
}
for i, ebnf := range ebnfs {
if parse(ebnf) == +1 {
fmt.Println("\ntests:")
for _, test := range tests[i] {
checkValid(test)
}
}
fmt.Println()
}
}</syntaxhighlight>
{{out}}
<pre>
parse:
"a" {
a = "a1" ( "a2" | "a3" ) { "a4" } [ "a5" ] "a6" ;
} "z" ===>
productions:
{{"a", 0, {{"terminal", "a1"}, {"or", {"terminal", "a2"}, {"terminal", "a3"}}, {"repeat", {"terminal", "a4"}}, {"optional", {"terminal", "a5"}}, {"terminal", "a6"}}}}
idents:
{"a"}
ididx:
{0}
extras:
{{"title", "a"}, {"comment", "z"}}
tests:
"a1a3a4a4a5a6", pass
"a1 a2a6", pass
"a1 a3 a4 a6", pass
"a1 a4 a5 a6", fail
"a1 a2 a4 a5 a5 a6", fail
"a1 a2 a4 a5 a6 a7", fail
"your ad here", fail
parse:
{
expr = term { plus term } .
term = factor { times factor } .
factor = number | '(' expr ')' .
plus = "+" | "-" .
times = "*" | "/" .
number = digit { digit } .
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
} ===>
productions:
{{"expr", 0, {{"ident", "term", 1}, {"repeat", {{"ident", "plus", 2}, {"ident", "term", 1}}}}}, {"term", 1, {{"ident", "factor", 3}, {"repeat", {{"ident", "times", 4}, {"ident", "factor", 3}}}}}, {"factor", 3, {"or", {"ident", "number", 5}, {{"terminal", "("}, {"ident", "expr", 0}, {"terminal", ")"}}}}, {"plus", 2, {"or", {"terminal", "+"}, {"terminal", "-"}}}, {"times", 4, {"or", {"terminal", "*"}, {"terminal", "/"}}}, {"number", 5, {{"ident", "digit", 6}, {"repeat", {"ident", "digit", 6}}}}, {"digit", 6, {"or", {"terminal", "0"}, {"terminal", "1"}, {"terminal", "2"}, {"terminal", "3"}, {"terminal", "4"}, {"terminal", "5"}, {"terminal", "6"}, {"terminal", "7"}, {"terminal", "8"}, {"terminal", "9"}}}}
idents:
{"expr", "term", "plus", "factor", "times", "number", "digit"}
ididx:
{0, 1, 3, 2, 4, 5, 6}
extras:
{}
tests:
"2", pass
"2*3 + 4/23 - 7", pass
"(3 + 4) * 6-2+(4*(4))", pass
"-2", fail
"3 +", fail
"(4 + 3", fail
parse:
a = "1" ===>
invalid ebnf (missing opening {)
parse:
{ a = "1" ; ===>
invalid ebnf (missing closing })
parse:
{ hello world = "1"; } ===>
invalid ebnf (= expected)
parse:
{ foo = bar . } ===>
invalid ebnf (undefined:bar)
</pre>
=={{header|Haskell}}==
We use Parsec to generate Parsec.
<
import Control.Monad
import Data.Maybe
Line 177 ⟶ 808:
lc c = char c <* ws
ws = many $ oneOf " \n\t"</
=={{header|Julia}}==
Creates a Grammar struct from an EBNF grammar, which has a matching Regex for each production of the EBNF grammar.
Tested with Julia v1.7.2
<syntaxhighlight lang="julia">
struct Grammar
regex::Regex
rules::Dict{Symbol,Regex}
root::Regex
function Grammar(regex::Regex)
names = keys(match(regex, ""))
new(regex,
Dict{Symbol,Regex}(
Symbol(name) => Regex(
"$(regex.pattern)(?&$(name))",
regex.compile_options,
regex.match_options
)
for name in names if name isa String),
Regex(
"$(regex.pattern)^\\s*(?&$(first(names)))\\s*\$",
regex.compile_options,
regex.match_options))
end
end
Base.getindex(grammar::Grammar, key) = grammar.rules[key]
Base.occursin(grammar::Grammar, str::AbstractString) = occursin(grammar.root, str)
Base.show(io::IO, grammar::Grammar) = print(io, "Grammar(", grammar.regex, ")")
const ebnfgrammar = Grammar(r"""
(?(DEFINE) # EBNF syntax
(?<syntax>
(?&title)? \s*+ { \s*+ ( (?&production) \s*+ )* } \s*+ (?&comment)? )
(?<production>
(?&identifier) \s*+ = \s*+ (?&expression) \s*+ [.;] )
(?<expression>
(?&term) ( \s*+ \| \s*+ (?&term) )* )
(?<term>
(?&factor) ( \s*+ (?&factor) )* )
(?<factor>
(?&identifier)
| (?&literal)
| \[ \s*+ (?&expression) \s*+ \]
| \( \s*+ (?&expression) \s*+ \)
| { \s*+ (?&expression) \s*+ } )
(?<identifier>
[^'"\s=|(){}[\].;]+ )
(?<title>
(?&literal) )
(?<comment>
(?&literal) )
(?<literal>
' [^']+ '
| " [^"]+ " )
)"""x)
function syntax(grammar::Grammar, str::AbstractString)
if occursin(grammar[:syntax], str)
"""(?(DEFINE)$(join(production(grammar, eachmatch(grammar[:production], str)))))"""
else
throw(ErrorException("Invalid EBNF syntax."))
end
end
production(grammar::Grammar, iter) = (production(grammar, m.match) for m in iter)
function production(grammar::Grammar, str::AbstractString)
rstrip(c -> isspace(c) || c == '.' || c == ';', str)
id, expr = split(str, r"\s*=\s*", limit=2)
"(?<$(id)>" * join(
expression(grammar, eachmatch(grammar[:expression], expr)),
"\\s*+|\\s*+") * "\\s*+)"
end
expression(grammar::Grammar, iter) = (expression(grammar, m.match) for m in iter)
function expression(grammar::Grammar, str::AbstractString)
join(term(grammar, eachmatch(grammar[:term], str)), "\\s*+|\\s*+")
end
term(grammar::Grammar, iter) = (term(grammar, m.match) for m in iter)
function term(grammar::Grammar, str::AbstractString)
join(factor(grammar, eachmatch(grammar[:factor], str)), "\\s*+")
end
factor(grammar::Grammar, iter) = (factor(grammar, m.match) for m in iter)
function factor(grammar::Grammar, str::AbstractString)
str = strip(str)
if startswith(str, r"['\"]")
literal(grammar, str)
elseif startswith(str, r"[[({]")
"(\\s*+" * expression(grammar, str[begin+1:end-1]) * (
if startswith(str, '[')
"\\s*+)?"
elseif startswith(str, '{')
"\\s*+)*"
else
"\\s*+)"
end
)
else
"(?&$(str))"
end
end
literal(::Grammar, str::AbstractString) = "\\Q$(str[begin+1:end-1])\\E"
grammar(ebnf::AbstractString) = Grammar(Regex(syntax(ebnfgrammar, ebnf)))
using Test
oneliner = grammar("""
"a" {
a = "a1" ( "a2" | "a3" ) { "a4" } [ "a5" ] "a6" ;
} "z"
""")
@testset "One liner" begin
@test occursin(oneliner, "a1a3a4a4a5a6")
@test occursin(oneliner, "a1 a2a6")
@test occursin(oneliner, "a1 a3 a4 a6")
@test !occursin(oneliner, "a1 a4 a5 a6")
@test !occursin(oneliner, "a1 a2 a4 a5 a5 a6")
@test !occursin(oneliner, "a1 a2 a4 a5 a6 a7")
@test !occursin(oneliner, "your ad here")
end
arithmetic = grammar("""
{
expr = term { plus term } .
term = factor { times factor } .
factor = number | '(' expr ')' .
plus = "+" | "-" .
times = "*" | "/" .
number = digit { digit } .
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
}
""")
@testset "Arithmetic expressions" begin
@test occursin(arithmetic, "2")
@test occursin(arithmetic, "2*3 + 4/23 - 7")
@test occursin(arithmetic, "(3 + 4) * 6-2+(4*(4))")
@test !occursin(arithmetic, "-2")
@test !occursin(arithmetic, "3 +")
@test !occursin(arithmetic, "(4 + 3")
end
@testset "Invalid EBNF" begin
@test_throws ErrorException grammar("""a = "1";""")
@test_throws ErrorException grammar("""{ a = "1";""")
@test_throws ErrorException grammar("""{ hello world = "1"; }""")
@test_throws ErrorException grammar("{ foo = bar . }")
end
</syntaxhighlight>
=={{header|Modula-2}}==
<
FROM ASCII IMPORT EOL;
Line 268 ⟶ 1,060:
Tabulate (T0);
Tabulate (T1);
END EBNF.</
And the source for the EBNF scanner. I hope you like nested procedures.
<
FROM ASCII IMPORT LF;
Line 437 ⟶ 1,229:
Ino := 0;
ch := ' '
END EBNFScanner.</
=={{header|Perl
<syntaxhighlight lang="perl">#!/usr/bin/perl
use strict; # http://www.rosettacode.org/wiki/Parse_EBNF
use warnings;
$SIG{__WARN__} = sub { print "\nWARN: @_\n"; exit };
my $h = qr/\G\s*/;
my $identifier = qr/$h([a-z]\w*)\b/i;
my $literal = qr/$h(['"])(.+?)\1/s;
my ($title, $comment, %productions, %called, $startsymbol, $show, $errpos);
sub node { bless [ @_[1..$#_] ], $_[0] }
sub err { die "ERROR: ", s/\G\s*\K/<**ERROR @_**>/r, "\n" }
sub want { /$h\Q$_[1]\E/gc ? shift : err "missing '$_[1]' " }
sub addin { node $_[0] => ref $_[1] eq $_[0] ? @{$_[1]} : $_[1], pop }
for my $case ( split /^-{50}.*\n/m, do { local $/; @ARGV ? <> : <DATA> } )
{
$show = $case =~ s/^#show.*//m;
my ($ebnf, $tests) = map s/^#.*\n//gmr, split /^#test.*\n/m, $case, 2;
parse( $ebnf, ($tests // "") =~ /.*\n/g );
}
sub parse
{
eval
{
(%productions, %called, $startsymbol) = ();
local $_ = shift // 'empty ebnf source string';
print '-' x 75, "\n", s/\s*\z/\n\n/r;
syntax(); ################################################## parse the EBNF
print " title: $title\n comment: $comment\n";
$startsymbol or err "no productions";
print "start symbol: $startsymbol\n";
for my $key ( sort keys %productions )
{
$show and print "\n$key =\n", $productions{$key}->show =~ s/^/ /gmr;
}
delete @called{keys %productions};
%called and die "\nERROR: undefined production(s) <@{[ keys %called]}>\n";
for ( @_ ) ###################################################### run tests
{
$errpos = undef;
print "\ntry: $_";
print eval
{
$productions{$startsymbol}->run or pos($_) = $errpos, err; ### run tree
/$h\n/gc or err 'incomplete parse';
} ? "valid\n" : $@;
}
1;
} or print "$@\n";
}
sub syntax ############################################## subs for parsing EBNF
{
$title = /$literal/gc ? $2 : 'none';
/$h\{/gc or err 'missing open brace';
while( /$identifier\s*=/gc ) # is this the start of a production
{
my $name = $1;
$startsymbol //= $name;
my $tree = expr(0);
$productions{$name} =
$productions{$name} ? addin ALT => $productions{$name}, $tree : $tree;
/$h[.;]/gc or err 'missing production terminator';
}
/$h\}/gc or err 'missing close brace';
$comment = /$literal/gc ? $2 : 'none';
/$h\z/gc or err 'extra characters after parse';
}
sub expr
{
my $tree =
/$identifier/gc ? do { $called{$1}++; node PROD => $1 } :
/$literal/gc ? node LIT => $2 :
/$h\[/gc ? node OPTION => want expr(0), ']' :
/$h\{/gc ? node REPEAT => want expr(0), '}' :
/$h\(/gc ? want expr(0), ')' :
err 'Invalid expression';
$tree =
/\G\s+/gc ? $tree :
$_[0] <= 1 && /\G(?=[[{('"a-z])/gci ? addin SEQ => $tree, expr(2) :
$_[0] <= 0 && /\G\|/gc ? addin ALT => $tree, expr(1) :
return $tree while 1;
}
################################################### run parse tree
sub LIT::run { /$h\Q$_[0][0]\E/gc }
sub SEQ::run
{
my $pos = pos($_) // 0;
for my $node ( @{ $_[0] } )
{
$node->run or $errpos = pos($_), pos($_) = $pos, return 0;
}
return 1;
}
sub OPTION::run
{
my $pos = pos($_) // 0;
$_[0][0]->run or pos($_) = $pos, return 1;
}
sub PROD::run
{
$productions{ $_[0][0] }->run;
}
sub REPEAT::run
{
my $pos = pos($_) // 0;
$pos = pos($_) while $_[0][0]->run;
pos($_) = $pos;
return 1;
}
sub ALT::run
{
my $pos = pos($_) // 0;
for my $node ( @{ $_[0] } )
{
eval{ $node->run } and return 1;
pos($_) = $pos;
}
return 0;
}
sub LIT::show { "LIT $_[0][0]\n" } ###################### for nested tree print
sub PROD::show { "PROD $_[0][0]\n" }
sub UNIVERSAL::show
{
join '', ref $_[0], "\n", map $_->show =~ s/^/ /gmr, @{ $_[0] };
}
__DATA__
"a" {
a = "a1" ( "a2" | "a3" ) { "a4" } [ "a5" ] "a6" ;
} "z"
#show
#tests
a1a3a4a4a5a6
a1 a2a6
a1 a3 a4 a6
a1 a4 a5 a6
a1 a2 a4 a5 a5 a6
a1 a2 a4 a5 a6 a7
your ad here
----------------------------------------------------------------------
"Arithmetic expressions" {
expr = term { plus term } .
term = factor { times factor } .
factor = number | '(' expr ')' .
plus = "+" | "-" .
times = "*" | "/" .
number = digit { digit } .
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
} 'http://www.rosettacode.org/wiki/Parse_EBNF'
#tests
2
2*3 + 4/23 - 7
(3 + 4) * 6-2+(4*(4))
-2
3 +
(4 + 3
----------------------------------------------------------------------
'some invalid EBNF' { a = "1" ;
----------------------------------------------------------------------
a = "1";
----------------------------------------------------------------------
{ hello world = "1"; }
----------------------------------------------------------------------
{ foo = bar . } "undefined production check"
----------------------------------------------------------------------</syntaxhighlight>
{{out}}
<pre>
---------------------------------------------------------------------------
"a" {
a = "a1" ( "a2" | "a3" ) { "a4" } [ "a5" ] "a6" ;
} "z"
title: a
comment: z
start symbol: a
a =
SEQ
LIT a1
ALT
LIT a2
LIT a3
REPEAT
LIT a4
OPTION
LIT a5
LIT a6
try: a1a3a4a4a5a6
valid
try: a1 a2a6
valid
try: a1 a3 a4 a6
valid
try: a1 a4 a5 a6
ERROR: a1 <**ERROR **>a4 a5 a6
try: a1 a2 a4 a5 a5 a6
ERROR: a1 a2 a4 a5 <**ERROR **>a5 a6
try: a1 a2 a4 a5 a6 a7
ERROR: a1 a2 a4 a5 a6 <**ERROR incomplete parse**>a7
try: your ad here
ERROR: <**ERROR **>your ad here
---------------------------------------------------------------------------
"Arithmetic expressions" {
expr = term { plus term } .
term = factor { times factor } .
factor = number | '(' expr ')' .
plus = "+" | "-" .
times = "*" | "/" .
number = digit { digit } .
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
} 'http://www.rosettacode.org/wiki/Parse_EBNF'
title: Arithmetic expressions
comment: http://www.rosettacode.org/wiki/Parse_EBNF
start symbol: expr
try: 2
valid
try: 2*3 + 4/23 - 7
valid
try: (3 + 4) * 6-2+(4*(4))
valid
try: -2
ERROR: <**ERROR **>-2
try: 3 +
ERROR: 3 <**ERROR incomplete parse**>+
try: (4 + 3
ERROR: <**ERROR **>(4 + 3
---------------------------------------------------------------------------
'some invalid EBNF' { a = "1" ;
ERROR: 'some invalid EBNF' { a = "1" ;
<**ERROR missing close brace**>
---------------------------------------------------------------------------
a = "1";
ERROR: <**ERROR missing open brace**>a = "1";
---------------------------------------------------------------------------
{ hello world = "1"; }
ERROR: { <**ERROR missing close brace**>hello world = "1"; }
---------------------------------------------------------------------------
{ foo = bar . } "undefined production check"
title: none
comment: undefined production check
start symbol: foo
ERROR: undefined production(s) <bar>
</pre>
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">src</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sdx</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">token</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">error</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">invalid</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">msg</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">error</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">msg</span>
<span style="color: #000000;">sdx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span> <span style="color: #000080;font-style:italic;">-- (set to eof)</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">skip_spaces</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">sdx</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">src</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sdx</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\t'</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\r'</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">})</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">sdx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
<span style="color: #000080;font-style:italic;">-- yeilds a single character token, one of {}()[]|=.;
-- or {"terminal",string} or {"ident", string} or -1.</span>
<span style="color: #000000;">skip_spaces</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">sdx</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">token</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">return</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">tokstart</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sdx</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"{}()[]|=.;"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">sdx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">token</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'\"'</span>
<span style="color: #008080;">or</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">=</span><span style="color: #008000;"><nowiki>'\''</nowiki></span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">closech</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">tokend</span><span style="color: #0000FF;">=</span><span style="color: #000000;">sdx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">src</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tokend</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">closech</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">sdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tokend</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
<span style="color: #000000;">token</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"terminal"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">src</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tokstart</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">tokend</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]}</span>
<span style="color: #008080;">return</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">token</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">invalid</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"no closing quote"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">>=</span><span style="color: #008000;">'a'</span> <span style="color: #008080;">and</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;"><=</span><span style="color: #008000;">'z'</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- to simplify things for the purposes of this task,
-- identifiers are strictly a-z only, not A-Z or 1-9</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">sdx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">sdx</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">src</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sdx</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;"><</span><span style="color: #008000;">'a'</span> <span style="color: #008080;">or</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">></span><span style="color: #008000;">'z'</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">token</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"ident"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">src</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tokstart</span><span style="color: #0000FF;">..</span><span style="color: #000000;">sdx</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]}</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">token</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">invalid</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"invalid ebnf"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">match_token</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">ch</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">token</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">invalid</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"invalid ebnf (%c expected)"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">idents</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span>
<span style="color: #000000;">ididx</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">add_ident</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">ident</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ident</span><span style="color: #0000FF;">,</span><span style="color: #000000;">idents</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">idents</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">idents</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ident</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">idents</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">ididx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ididx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">k</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">forward</span> <span style="color: #008080;">function</span> <span style="color: #000000;">expression</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">factor</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">token</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">"ident"</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">token</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">add_ident</span><span style="color: #0000FF;">(</span><span style="color: #000000;">token</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">token</span>
<span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'['</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"optional"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">expression</span><span style="color: #0000FF;">()}</span>
<span style="color: #000000;">match_token</span><span style="color: #0000FF;">(</span><span style="color: #008000;">']'</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'('</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">expression</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">match_token</span><span style="color: #0000FF;">(</span><span style="color: #008000;">')'</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'{'</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"repeat"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">expression</span><span style="color: #0000FF;">()}</span>
<span style="color: #000000;">match_token</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'}'</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- erm??
-- res = -1 -- ""</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">term</span><span style="color: #0000FF;">()</span>
<span style="color: #000080;font-style:italic;">-- sequence res = {"factors",factor()} -- (opted against this)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">factor</span><span style="color: #0000FF;">()}</span>
<span style="color: #008080;">while</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">token</span><span style="color: #0000FF;">,{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'|'</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'.'</span><span style="color: #0000FF;">,</span><span style="color: #008000;">';'</span><span style="color: #0000FF;">,</span><span style="color: #008000;">')'</span><span style="color: #0000FF;">,</span><span style="color: #008000;">']'</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'}'</span><span style="color: #0000FF;">})</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">factor</span><span style="color: #0000FF;">())</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">expression</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">term</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'|'</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"or"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'|'</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">term</span><span style="color: #0000FF;">())</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">productions</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">production</span><span style="color: #0000FF;">()</span>
<span style="color: #000080;font-style:italic;">-- returns a token or -1; the real result is left in productions[] etc.</span>
<span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">!=</span><span style="color: #008000;">'}'</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">invalid</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"invalid ebnf (missing closing })"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">token</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">or</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]!=</span><span style="color: #008000;">"ident"</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">ident</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">add_ident</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ident</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">match_token</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'='</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">expression</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">productions</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">productions</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">ident</span><span style="color: #0000FF;">,</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">ididx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">productions</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">token</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">extras</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">parse</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">ebnf</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- returns: +1 if ok, -1 if bad</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"parse: "</span><span style="color: #0000FF;">&</span><span style="color: #000000;">ebnf</span><span style="color: #0000FF;">&</span><span style="color: #008000;">" ===>\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">error</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #000000;">src</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ebnf</span>
<span style="color: #000000;">sdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">idents</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #000000;">ididx</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #000000;">productions</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #000000;">extras</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">token</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">token</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"title"</span>
<span style="color: #000000;">extras</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">extras</span><span style="color: #0000FF;">,</span><span style="color: #000000;">token</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">!=</span><span style="color: #008000;">'{'</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">invalid</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"invalid ebnf (missing opening {)"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">token</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">production</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'}'</span> <span style="color: #008080;">or</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">token</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">token</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"comment"</span>
<span style="color: #000000;">extras</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">extras</span><span style="color: #0000FF;">,</span><span style="color: #000000;">token</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">get_token</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">token</span><span style="color: #0000FF;">!=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">invalid</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"invalid ebnf (missing eof?)"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">error</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ididx</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">invalid</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"invalid ebnf (undefined:"</span><span style="color: #0000FF;">&</span><span style="color: #000000;">idents</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]&</span><span style="color: #008000;">")"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">ppOpt</span><span style="color: #0000FF;">({</span><span style="color: #004600;">pp_Pause</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">})</span>
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">productions</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- pp(idents)
-- pp(ididx)
-- pp(extras)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #000080;font-style:italic;">-- The rules that applies() has to deal with are:
-- {factors} - if rule[1] is not string, just apply one after the other,
-- recursively. As per term() above, originally had "factors",
-- but getting rid of it made the syntax tree much clearer)
-- {"terminal", "a1"} -- literal constants
-- {"or", <e1>, <e2>, ...} -- (any) one of n
-- {"repeat", <e1>} -- as per "{}" in ebnf
-- {"optional", <e1>} -- as per "[]" in ebnf
-- {"ident", <name>, idx} -- apply the sub-rule</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">applies</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">rule</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">was_sdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sdx</span> <span style="color: #000080;font-style:italic;">-- in case of failure</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">r1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rule</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #004080;">string</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rule</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">applies</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rule</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">sdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">was_sdx</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">r1</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"terminal"</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">skip_spaces</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rule</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">sdx</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">or</span> <span style="color: #000000;">src</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sdx</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">rule</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">][</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">sdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">was_sdx</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">sdx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">r1</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"or"</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rule</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">applies</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rule</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">sdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">was_sdx</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">r1</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"repeat"</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">applies</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rule</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">r1</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"optional"</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">applies</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rule</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">r1</span><span style="color: #0000FF;">=</span><span style="color: #008000;">"ident"</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rule</span><span style="color: #0000FF;">[</span><span style="color: #000000;">3</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">ii</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ididx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">applies</span><span style="color: #0000FF;">(</span><span style="color: #000000;">productions</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ii</span><span style="color: #0000FF;">][</span><span style="color: #000000;">3</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">sdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">was_sdx</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">else</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">check_valid</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">src</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">test</span>
<span style="color: #000000;">sdx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">applies</span><span style="color: #0000FF;">(</span><span style="color: #000000;">productions</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">3</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">skip_spaces</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">sdx</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #0000FF;">?{</span><span style="color: #000000;">test</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"pass"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"fail"</span><span style="color: #0000FF;">}[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">-</span><span style="color: #000000;">res</span><span style="color: #0000FF;">]}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">ebnf</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"""
"a" {
a = "a1" ( "a2" | "a3" ) { "a4" } [ "a5" ] "a6" ;
} "z" """</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"""
{
expr = term { plus term } .
term = factor { times factor } .
factor = number | '(' expr ')' .
plus = "+" | "-" .
times = "*" | "/" .
number = digit { digit } .
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
}"""</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">`a = "1"`</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">`{ a = "1" ;`</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">`{ hello world = "1"; }`</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">`{ foo = bar . }`</span>
<span style="color: #0000FF;">}</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"a1a3a4a4a5a6"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"a1 a2a6"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"a1 a3 a4 a6"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"a1 a4 a5 a6"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"a1 a2 a4 a5 a5 a6"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"a1 a2 a4 a5 a6 a7"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"your ad here"</span><span style="color: #0000FF;">},</span>
<span style="color: #0000FF;">{</span><span style="color: #008000;">"2"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"2*3 + 4/23 - 7"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"(3 + 4) * 6-2+(4*(4))"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"-2"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"3 +"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"(4 + 3"</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ebnf</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">parse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ebnf</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])=+</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">?</span><span style="color: #008000;">"tests:"</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">check_valid</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
In real use, I would be tempted to use numeric literals rather than string tags in such structures, but the latter certainly make things ten times easier to debug, plus I got an instantly legible syntax tree dump (the bit just after "===>" below) practically for free.
{{out}}
<pre>
parse:
"a" {
a = "a1" ( "a2" | "a3" ) { "a4" } [ "a5" ] "a6" ;
} "z" ===>
{{"a", 1,
{{"terminal", "a1"}, {"or", {"terminal", "a2"}, {"terminal", "a3"}},
{"repeat", {"terminal", "a4"}}, {"optional", {"terminal", "a5"}},
{"terminal", "a6"}}}}
"tests:"
{"a1a3a4a4a5a6","pass"}
{"a1 a2a6","pass"}
{"a1 a3 a4 a6","pass"}
{"a1 a4 a5 a6","fail"}
{"a1 a2 a4 a5 a5 a6","fail"}
{"a1 a2 a4 a5 a6 a7","fail"}
{"your ad here","fail"}
parse:
{
expr = term { plus term } .
term = factor { times factor } .
factor = number | '(' expr ')' .
plus = "+" | "-" .
times = "*" | "/" .
number = digit { digit } .
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
} ===>
{{"expr", 1,
{{"ident", "term", 2},
{"repeat", {{"ident", "plus", 3}, {"ident", "term", 2}}}}},
{"term", 2,
{{"ident", "factor", 4},
{"repeat", {{"ident", "times", 5}, {"ident", "factor", 4}}}}},
{"factor", 4,
{"or", {"ident", "number", 6},
{{"terminal", "("}, {"ident", "expr", 1}, {"terminal", ")"}}}},
{"plus", 3, {"or", {"terminal", "+"}, {"terminal", "-"}}},
{"times", 5, {"or", {"terminal", "*"}, {"terminal", "/"}}},
{"number", 6, {{"ident", "digit", 7}, {"repeat", {"ident", "digit", 7}}}},
{"digit", 7,
{"or", {"terminal", "0"}, {"terminal", "1"}, {"terminal", "2"},
{"terminal", "3"}, {"terminal", "4"}, {"terminal", "5"},
{"terminal", "6"}, {"terminal", "7"}, {"terminal", "8"},
{"terminal", "9"}}}}
"tests:"
{"2","pass"}
{"2*3 + 4/23 - 7","pass"}
{"(3 + 4) * 6-2+(4*(4))","pass"}
{"-2","fail"}
{"3 +","fail"}
{"(4 + 3","fail"}
parse: a = "1" ===>
"invalid ebnf (missing opening {)"
parse: { a = "1" ; ===>
"invalid ebnf (missing closing })"
parse: { hello world = "1"; } ===>
"invalid ebnf (= expected)"
parse: { foo = bar . } ===>
"invalid ebnf (undefined:bar)"
</pre>
=={{header|PicoLisp}}==
<syntaxhighlight lang="picolisp">(de EBNF
"expr : term ( ( PLUS | MINUS ) term )* ;"
"term : factor ( ( MULT | DIV ) factor )* ;"
"factor : NUMBER ;" )
(for E EBNF
(use (@S @E)
(unless (and (match '(@S : @E ;) (str E)) (not (cdr @S)))
(quit "Invalid EBNF" E) )
(put (car @S) 'ebnf @E) ) )</syntaxhighlight>
<syntaxhighlight lang="picolisp">(de matchEbnf (Pat)
(cond
((asoq Pat '((PLUS . +) (MINUS . -) (MULT . *) (DIV . /)))
(let Op (cdr @)
(when (= Op (car *Lst))
(pop '*Lst)
Op ) ) )
((== 'NUMBER Pat)
(cond
((num? (car *Lst))
(pop '*Lst)
@ )
((and (= "-" (car *Lst)) (num? (cadr *Lst)))
(setq *Lst (cddr *Lst))
(- @) ) ) )
((get Pat 'ebnf) (parseLst @))
((atom Pat))
(T
(loop
(T (matchEbnf (pop 'Pat)) @)
(NIL Pat)
(NIL (== '| (pop 'Pat)))
(NIL Pat) ) ) ) )
(de parseLst (Pat)
(let (P (pop 'Pat) X (matchEbnf P))
(loop
(NIL Pat)
(if (n== '* (cadr Pat))
(if (matchEbnf (pop 'Pat))
(setq X (list @ X))
(throw) )
(loop
(NIL *Lst)
(NIL (matchEbnf (car Pat)))
(setq X (list @ X (or (matchEbnf P) (throw)))) )
(setq Pat (cddr Pat)) ) )
X ) )
(de parseEbnf (Str)
(let *Lst (str Str "")
(catch NIL
(parseLst (get 'expr 'ebnf)) ) ) )</syntaxhighlight>
Output:
<pre>: (parseEbnf "1 + 2 * -3 / 7 - 3 * 4")
-> (- (+ 1 (/ (* 2 -3) 7)) (* 3 4))</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2019.03.1}}
This parses the EBNF rule set using a Raku grammar, then if it parses as valid EBNF, constructs a grammar and parses the test strings with that. EBNF rule sets that are naively syntactically correct but missing rules will parse as valid but will give a runtime failure warning about missing methods.
It is implemented and exercised using the flavor of EBNF and test cases specified on the [[Parse EBNF/Tests|test page]].
<syntaxhighlight lang="raku" line># A Raku grammar to parse EBNF
grammar EBNF {
rule TOP { ^ <title>? '{' [ <production> ]+ '}' <comment>? $ }
rule production { <name> '=' <expression> <[.;]> }
rule expression { <term> +% "|" }
rule term { <factor>+ }
rule factor { <group> | <repeat> | <optional> | <identifier> | <literal> }
rule group { '(' <expression> ')' }
rule repeat { '{' <expression> '}' }
rule optional { '[' <expression> ']' }
token identifier { <-[\|\(\)\{\}\[\]\.\;\"\'\s]>+ }
token literal { ["'" <-[']>+ "'" | '"' <-["]>+ '"'] } #
token title { <literal> }
token comment { <literal> }
token name { <identifier> <?before \h* '='> }
}
class EBNF::Actions {
method TOP($/) {
($<title> ?? $<title>.subst(/\W/, '', :g)
" \{\n rule TOP \{^[<" ~ $/<production>[0]<name> ~
">]+\$\}\n " ~ $<production>>>.ast ~ "\}"
}
}
}
}
Line 512 ⟶ 2,036:
term = factor { times factor } .
factor = number | '(' expr ')' .
plus = "+" | "-" .
times = "*" | "/" .
number = digit { digit } .
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
Line 550 ⟶ 2,074:
my $i = 1;
for @tests -> $test {
unless EBNF.parse($test<ebnf>) {
say "Parsing EBNF grammar:\n";
Line 559 ⟶ 2,081:
next;
}
my $p = EBNF.parse($test<ebnf>, :actions(EBNF::Actions));
my $grammar = $p.ast;
Line 565 ⟶ 2,086:
my $title = $0;
my $fn = 'EBNFtest'~$i++;
my $fh = open($fn, :w)
$fh.say( "\{\n", $grammar );
$fh.say( qq|say "Parsing EBNF grammar '$title':\\n";| );
$fh.say( qq|say q<{$test<ebnf>.subst(/^^\h*/,'',:g)}>;| );
$fh.say( q|say "\nValid syntax.\n\nTesting:\n";| );
$fh.say( q|CATCH {
my $len =
for $test<teststrings>.flat -> $s {
$fh.say( qq|printf "%{$len}s", '{$s}';
qq|printf " - %s\\n",
qq| ?? 'valid.' !! 'NOT valid.';|
);
}
$fh.say( qq| "\\n"} |);
$fh.close;
say qqx/
say '*' x 79, "\n";
unlink $fn;
}</syntaxhighlight>
Output:
<pre>
Syntax Tree:
a = "a1" ( "a2" | "a3" ) { "a4" } [ "a5" ] "a6" ;
} "z"
title =>
literal =>
production =>
name =>
identifier =>
expression =>
term =>
factor =>
literal =>
factor =>
group =>
expression =>
term =>
factor =>
literal =>
term =>
factor =>
literal =>
factor =>
repeat =>
expression =>
term =>
factor =>
literal =>
factor =>
optional =>
expression =>
term =>
factor =>
literal =>
factor =>
literal =>
comment =>
literal =>
Parsing EBNF grammar 'a':
Line 648 ⟶ 2,168:
*******************************************************************************
Syntax Tree:
expr = term { plus term } .
term = factor { times factor } .
Line 660 ⟶ 2,180:
number = digit { digit } .
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
}
production =>
name =>
identifier =>
expression =>
term =>
factor =>
identifier =>
factor =>
repeat =>
expression =>
term =>
factor =>
identifier =>
factor =>
identifier =>
production =>
name =>
identifier =>
expression =>
term =>
factor =>
identifier =>
factor =>
repeat =>
expression =>
term =>
factor =>
identifier =>
factor =>
identifier =>
production =>
name =>
identifier =>
expression =>
term =>
factor =>
identifier =>
term =>
factor =>
literal =>
factor =>
identifier =>
factor =>
literal =>
production =>
name =>
identifier =>
expression =>
term =>
factor =>
literal =>
term =>
factor =>
literal =>
production =>
name =>
identifier =>
expression =>
term =>
factor =>
literal =>
term =>
factor =>
literal =>
production =>
name =>
identifier =>
expression =>
term =>
factor =>
identifier =>
factor =>
repeat =>
expression =>
term =>
factor =>
identifier =>
production =>
name =>
identifier =>
expression =>
term =>
factor =>
literal =>
term =>
factor =>
literal =>
term =>
factor =>
literal =>
term =>
factor =>
literal =>
term =>
factor =>
literal =>
term =>
factor =>
literal =>
term =>
factor =>
literal =>
term =>
factor =>
literal =>
term =>
factor =>
literal =>
term =>
factor =>
literal =>
Parsing EBNF grammar 'unnamed':
Line 808 ⟶ 2,328:
*******************************************************************************
Parsing EBNF grammar:
Line 815 ⟶ 2,335:
Invalid syntax. Can not be parsed.
*******************************************************************************
Parsing EBNF grammar:
Line 823 ⟶ 2,342:
Invalid syntax. Can not be parsed.
*******************************************************************************
Parsing EBNF grammar:
Line 831 ⟶ 2,349:
Invalid syntax. Can not be parsed.
*******************************************************************************
Syntax Tree:
production =>
name =>
identifier =>
expression =>
term =>
factor =>
identifier =>
Parsing EBNF grammar 'unnamed':
Line 853 ⟶ 2,370:
foobar - No such method 'bar' for invocant of type 'unnamed'
*******************************************************************************</pre>
=={{header|Ruby}}==
{{in progress|lang=Ruby|day=12|month=May|year=2011}}
{{incomplete|Ruby|The tokenizer is here, but the parser is very incomplete.}}
<
# The tokenizer splits the input into Tokens like "identifier",
# ":", ")*" and so on. This design uses a StringScanner on each line of
Line 1,055 ⟶ 2,513:
parse
end
</syntaxhighlight>
=={{header|Tcl}}==
Line 1,061 ⟶ 2,519:
Demonstration lexer and parser. Note that this parser supports parenthesized expressions, making the grammar recursive.
<
# Utilities to make the coroutine easier to use
Line 1,195 ⟶ 2,653:
}
throw SYNTAX "\"$payload\" at position $index"
}</
<
puts [parse "1 - 2 - -3 * 4 + 5"]
puts [parse "1 - 2 - -3 * (4 + 5)"]</
Output:
<pre>
PLUS {MINUS {MINUS 1 2} {MULT -3 4}} 5
MINUS {MINUS 1 2} {MULT -3 {PLUS 4 5}}
</pre>
=={{header|Wren}}==
{{trans|Phix}}
{{libheader|Wren-fmt}}
{{libheader|Wren-iterate}}
{{libheader|Wren-str}}
{{libheader|Wren-seq}}
Translated via the Go entry.
<syntaxhighlight lang="wren">import "./fmt" for Conv, Fmt
import "./iterate" for Stepped
import "./str" for Char
import "./seq" for Lst
var src = ""
var ch = ""
var sdx = 0
var token = null
var isSeq = false
var err = false
var idents = []
var ididx = []
var productions = []
var extras = []
var results = ["pass", "fail"]
var invalid = Fn.new { |msg|
err = true
System.print(msg)
sdx = src.count // set to EOF
return -1
}
var skipSpaces = Fn.new {
while (true) {
if (sdx >= src.count) return
ch = src[sdx]
if (!" \t\r\n".contains(ch)) return
sdx = sdx + 1
}
}
var getToken = Fn.new {
// Yields a single character token, one of {}()[]|=.;
// or {"terminal",string} or {"ident", string} or -1.
skipSpaces.call()
if (sdx >= src.count) {
token = -1
isSeq = false
return
}
var tokstart = sdx
if ("{}()[]|=.;".contains(ch)) {
sdx = sdx + 1
token = ch
isSeq = false
} else if (ch == "\"" || ch == "'") {
var closech = ch
for (tokend in Stepped.ascend(sdx + 1...src.count)) {
if (src[tokend] == closech) {
sdx = tokend + 1
token = ["terminal", src[tokstart+1...tokend]]
isSeq = true
return
}
}
token = invalid.call("no closing quote")
isSeq = false
} else if (Char.isAsciiLower(ch)) {
// To simplify things for the purposes of this task,
// identifiers are strictly a-z only, not A-Z or 1-9.
while (true) {
sdx = sdx + 1
if (sdx >= src.count) break
ch = src[sdx]
if (!Char.isAsciiLower(ch)) break
}
token = ["ident", src[tokstart...sdx]]
isSeq = true
} else {
token = invalid.call("invalid ebnf")
isSeq = false
}
}
var matchToken = Fn.new { |ch|
if (token != ch) {
token = invalid.call("invalid ebnf (%(ch) expected)")
isSeq = false
} else {
getToken.call()
}
}
var addIdent = Fn.new { |ident|
var k = -1
var i = 0
for (id in idents) {
if (id == ident) {
k = i
break
}
i = i + 1
}
if (k == -1) {
idents.add(ident)
k = idents.count - 1
ididx.add(-1)
}
return k
}
var expression // forward declaration
var factor = Fn.new {
var res
if (isSeq) {
if (token[0] == "ident") {
var idx = addIdent.call(token[1])
token.add(idx)
}
res = token
getToken.call()
} else if (token == "[") {
getToken.call()
res = ["optional", expression.call()]
matchToken.call("]")
} else if (token == "(") {
getToken.call()
res = expression.call()
matchToken.call(")")
} else if (token == "{") {
getToken.call()
res = ["repeat", expression.call()]
matchToken.call("}")
} else {
Fiber.abort("invalid token in factor() function")
}
if (res is Sequence && res.count == 1) return res[0]
return res
}
var term = Fn.new {
var res = [factor.call()]
var tokens = [-1, "|", ".", ";", ")", "]", "}"]
while (true) {
var outer = false
for (t in tokens) {
if (t == token) {
outer = true
break
}
}
if (outer) break
res.add(factor.call())
}
if (res.count == 1) return res[0]
return res
}
// declared earlier
expression = Fn.new {
var res = [term.call()]
if (token == "|") {
res = ["or", res[0]]
while (token == "|") {
getToken.call()
res.add(term.call())
}
}
if (res.count == 1) return res[0]
return res
}
var production = Fn.new {
// Returns a token or -1; the real result is left in 'productions' etc,
getToken.call()
if (token != "}") {
if (token == -1) return invalid.call("invalid ebnf (missing closing })")
if (!isSeq) return -1
if (token[0] != "ident") return -1
var ident = token[1]
var idx = addIdent.call(ident)
getToken.call()
matchToken.call("=")
if (token == -1) return -1
productions.add([ident, idx, expression.call()])
ididx[idx] = productions.count - 1
}
return token
}
// Adjusts Wren's normal printing of lists to look more like Phix output.
var pprint = Fn.new { |ob, header|
Fmt.print("\n$s:", header)
var quote // recursive closure
quote = Fn.new { |list|
for (i in 0...list.count) {
if (list[i] is String) {
list[i] = Fmt.swrite("$q", list[i])
} else if (list[i] is List) quote.call(list[i])
}
}
var obs
if (ob is String) {
obs = Fmt.swrite("$q", ob)
} else if (ob is List) {
obs = Lst.clone(ob)
quote.call(obs)
}
var pp = obs.toString
pp = pp.replace("[", "{")
pp = pp.replace("]", "}")
for (i in 0...idents.count) {
var xs = Fmt.swrite("'\\x$02d'", i)
pp = pp.replace(xs, i.toString)
}
System.print(pp)
}
var parse = Fn.new { |ebnf|
// Returns +1 if ok, -1 if bad.
System.print("parse:\n%(ebnf) ===>")
err = false
src = ebnf
sdx = 0
idents.clear()
ididx.clear()
productions.clear()
extras.clear()
getToken.call()
if (isSeq) {
token[0] = "title"
extras.add(token)
getToken.call()
}
if (token != "{") return invalid.call("invalid ebnf (missing opening {)")
while (true) {
token = production.call()
if (token == "}" || token == -1) break
}
getToken.call()
if (isSeq) {
token[0] = "comment"
extras.add(token)
getToken.call()
}
if (token != -1) return invalid.call("invalid ebnf (missing eof?)")
if (err) return -1
var k = -1
var i = 0
for (idx in ididx) {
if (idx == -1) {
k = i
break
}
i = i + 1
}
if (k != -1) return invalid.call("invalid ebnf (undefined:%(idents[k]))")
pprint.call(productions, "productions")
pprint.call(idents, "idents")
pprint.call(ididx, "ididx")
pprint.call(extras, "extras")
return 1
}
// The rules that applies() has to deal with are:
// {factors} - if rule[0] is not string,
// just apply one after the other recursively.
// {"terminal", "a1"} -- literal constants
// {"or", <e1>, <e2>, ...} -- (any) one of n
// {"repeat", <e1>} -- as per "{}" in ebnf
// {"optional", <e1>} -- as per "[]" in ebnf
// {"ident", <name>, idx} -- apply the sub-rule
var applies // recursive function
applies = Fn.new { |rule|
var wasSdx = sdx // in case of failure
var r1 = rule[0]
if (!(r1 is String)) {
for (i in 0...rule.count) {
if (!applies.call(rule[i])) {
sdx = wasSdx
return false
}
}
} else if (r1 == "terminal") {
skipSpaces.call()
var r2 = rule[1]
for (i in 0...r2.count) {
if (sdx >= src.count || src[sdx] != r2[i]) {
sdx = wasSdx
return false
}
sdx = sdx + 1
}
} else if (r1 == "or") {
for (i in Stepped.ascend(1...rule.count)) {
if (applies.call(rule[i])) return true
}
sdx = wasSdx
return false
} else if (r1 == "repeat") {
while (applies.call(rule[1])) {}
} else if (r1 == "optional") {
applies.call(rule[1])
} else if (r1 == "ident") {
var i = rule[2]
var ii = ididx[i]
if (!(applies.call(productions[ii][2]))) {
sdx = wasSdx
return false
}
} else {
Fiber.abort("invalid rule in applies() function")
}
return true
}
var checkValid = Fn.new { |test|
src = test
sdx = 0
var res = applies.call(productions[0][2])
skipSpaces.call()
if (sdx < src.count) res = false
Fmt.print("$q, $s", test, results[1-Conv.btoi(res)])
}
var ebnfs = [
""""a" {
a = "a1" ( "a2" | "a3" ) { "a4" } [ "a5" ] "a6" ;
} "z" """,
"""{
expr = term { plus term } .
term = factor { times factor } .
factor = number | '(' expr ')' .
plus = "+" | "-" .
times = "*" | "/" .
number = digit { digit } .
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
}""",
"a = \"1\"",
"""{ a = "1" ;""",
"""{ hello world = "1"; }""",
"""{ foo = bar . }"""
]
var tests = [
[
"a1a3a4a4a5a6",
"a1 a2a6",
"a1 a3 a4 a6",
"a1 a4 a5 a6",
"a1 a2 a4 a5 a5 a6",
"a1 a2 a4 a5 a6 a7",
"your ad here"
],
[
"2",
"2*3 + 4/23 - 7",
"(3 + 4) * 6-2+(4*(4))",
"-2",
"3 +",
"(4 + 3"
]
]
var i = 0
for (ebnf in ebnfs) {
if (parse.call(ebnf) == 1) {
System.print("\ntests:")
for (test in tests[i]) checkValid.call(test)
}
System.print()
i = i + 1
}</syntaxhighlight>
{{out}}
<pre>
parse:
"a" {
a = "a1" ( "a2" | "a3" ) { "a4" } [ "a5" ] "a6" ;
} "z" ===>
productions:
{{"a", 0, {{"terminal", "a1"}, {"or", {"terminal", "a2"}, {"terminal", "a3"}}, {"repeat", {"terminal", "a4"}}, {"optional", {"terminal", "a5"}}, {"terminal", "a6"}}}}
idents:
{"a"}
ididx:
{0}
extras:
{{"title", "a"}, {"comment", "z"}}
tests:
"a1a3a4a4a5a6", pass
"a1 a2a6", pass
"a1 a3 a4 a6", pass
"a1 a4 a5 a6", fail
"a1 a2 a4 a5 a5 a6", fail
"a1 a2 a4 a5 a6 a7", fail
"your ad here", fail
parse:
{
expr = term { plus term } .
term = factor { times factor } .
factor = number | '(' expr ')' .
plus = "+" | "-" .
times = "*" | "/" .
number = digit { digit } .
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" .
} ===>
productions:
{{"expr", 0, {{"ident", "term", 1}, {"repeat", {{"ident", "plus", 2}, {"ident", "term", 1}}}}}, {"term", 1, {{"ident", "factor", 3}, {"repeat", {{"ident", "times", 4}, {"ident", "factor", 3}}}}}, {"factor", 3, {"or", {"ident", "number", 5}, {{"terminal", "("}, {"ident", "expr", 0}, {"terminal", ")"}}}}, {"plus", 2, {"or", {"terminal", "+"}, {"terminal", "-"}}}, {"times", 4, {"or", {"terminal", "*"}, {"terminal", "/"}}}, {"number", 5, {{"ident", "digit", 6}, {"repeat", {"ident", "digit", 6}}}}, {"digit", 6, {"or", {"terminal", "0"}, {"terminal", "1"}, {"terminal", "2"}, {"terminal", "3"}, {"terminal", "4"}, {"terminal", "5"}, {"terminal", "6"}, {"terminal", "7"}, {"terminal", "8"}, {"terminal", "9"}}}}
idents:
{"expr", "term", "plus", "factor", "times", "number", "digit"}
ididx:
{0, 1, 3, 2, 4, 5, 6}
extras:
{}
tests:
"2", pass
"2*3 + 4/23 - 7", pass
"(3 + 4) * 6-2+(4*(4))", pass
"-2", fail
"3 +", fail
"(4 + 3", fail
parse:
a = "1" ===>
invalid ebnf (missing opening {)
parse:
{ a = "1" ; ===>
invalid ebnf (missing closing })
parse:
{ hello world = "1"; } ===>
invalid ebnf (= expected)
parse:
{ foo = bar . } ===>
invalid ebnf (undefined:bar)
</pre>
| |||