EBNF

A grammar for writing grammars: the notation half the specifications on your shelf are written in, read by a grammar of its own.

1(* An arithmetic expression, written with all three brackets *)
2
3<expression> ::= <term> { ("+" | "-") <term> }
4<term>       ::= <factor> { ("*" | "/") <factor> }
5<factor>     ::= [ "-" ] <primary>
6<primary>    ::= <number> | <name> | "(" <expression> ")"

The interesting rule is Element, and the reason is the semicolon: EBNF ends a rule with one, except when it does not. Without it, the name opening the next rule looks exactly like a name used inside the current one, and a greedy reading would swallow the whole file into the first rule.

The way out is a predicate. !(Identifier() ::T_ASSIGN::) matches nothing and consumes nothing - it only asks whether what comes next is a name followed by ::=, and fails if it is. A name that opens a rule therefore cannot be read as part of the rule before it. See Predicates for what else they are good for.

Grammar

 1/**
 2 * -----------------------------------------------------------------------------
 3 *  EBNF
 4 * -----------------------------------------------------------------------------
 5 *
 6 * Backus-Naur form with the three brackets that make a repetition and an
 7 * option writable without a rule of their own.
 8 *
 9 * @see https://www.iso.org/standard/26153.html
10 */
11
12%pragma root RuleList
13
14%skip  T_WHITESPACE            \s++
15%skip  T_COMMENT               \(\*.*?\*\)
16
17%token T_ASSIGN                ::=|=
18%token T_ANGLE_OPEN            <
19%token T_ANGLE_CLOSE           >
20%token T_BRACKET_OPEN          \[
21%token T_BRACKET_CLOSE         \]
22%token T_BRACE_OPEN            \{
23%token T_BRACE_CLOSE           \}
24%token T_PARENTHESIS_OPEN      \(
25%token T_PARENTHESIS_CLOSE     \)
26%token T_OR                    \|
27%token T_SEMICOLON             ;
28%token T_COMMA                 ,
29
30%token T_STRING                "[^"]*+"|'[^']*+'
31%token T_NAME                  [a-zA-Z][a-zA-Z0-9_-]*+
32
33RuleList
34  : Rule()*
35  ;
36
37// <name> ::= alternatives
38Rule
39  : Identifier() ::T_ASSIGN:: Alternatives() ::T_SEMICOLON::?
40  ;
41
42Alternatives
43  : Alternative() (::T_OR:: Alternative())*
44  ;
45
46Alternative
47  : Element()*
48  ;
49
50/**
51 * A rule ends where the next one begins, and the semicolon closing it is
52 * optional, so a name followed by the separator opens a rule rather than
53 * belonging to the one before it.
54 */
55Element
56  : Optional()
57  | Repetition()
58  | Group()
59  | Terminal()
60  | !(Identifier() ::T_ASSIGN::) Identifier()
61  ;
62
63// [ ... ] - written none or one time
64Optional
65  : ::T_BRACKET_OPEN:: Alternatives() ::T_BRACKET_CLOSE:: ::T_COMMA::?
66  ;
67
68// { ... } - written none or more times
69Repetition
70  : ::T_BRACE_OPEN:: Alternatives() ::T_BRACE_CLOSE:: ::T_COMMA::?
71  ;
72
73// ( ... ) - read as one
74Group
75  : ::T_PARENTHESIS_OPEN:: Alternatives() ::T_PARENTHESIS_CLOSE:: ::T_COMMA::?
76  ;
77
78// <name> or name
79Identifier
80  : ::T_ANGLE_OPEN:: <T_NAME> ::T_ANGLE_CLOSE:: ::T_COMMA::?
81  | <T_NAME> ::T_COMMA::?
82  ;
83
84Terminal
85  : <T_STRING> ::T_COMMA::?
86  ;

Usage

1use Phplrt\Compiler\Compiler;
2use Phplrt\Source\File;
3
4$parser = new Compiler()
5    ->load(new File(__DIR__ . '/grammar.pp3'))
6    ->getParser();
7
8$rules = $parser->parse(new File(__DIR__ . '/expression.ebnf'));

Both spellings of everything are accepted on purpose: ::= and = for the separator, <name> and name for a reference, and the commas ISO 14977 insists on between elements are read and dropped wherever they turn up.

25+ more grammars. phplrt/grammars collects ready to read grammars for real languages - JSON5, TSV, semantic versions, DQL, PHQL, JMS types, PSR-5 and Doctrine annotations, Symfony expressions, Go! AOP pointcuts, Praspel contracts and more - each with sample inputs and a test that keeps it honest.