Go to the first, previous, next, last section, table of contents.
The first example grammar accepts a language of parentheses. The accepted sentences must be well-parenthesized. Examples of valid sentences are `()', `(())(())', `(()(()))', and `' (the empty sentence). Invalid sentences include `)', `(', and `((()())'.
This is the grammar for the language of parentheses:
%class ex1
language: expr*;
expr: '(' expr* ')';
The first line defines the class name of the parser that gp will
create. Incidentally, that name is also used as the name of the
directory in the distribution of this manual that contains this example.
To see this example in action, just cd to the directory `ex1'
and type make, followed by ./ex1.
The next line defines a rule of the grammar. Since it is the first rule in the grammar, it is the top rule and it defines the language that will be accepted by the grammar.
language: expr*;
This rule defines the expansion of the non-terminal language to
be expr* . The rule is terminated by a semicolon (;).
The `*' character is one of several postfix operators that modify
how the preceding entity is to be matched. Without any operators, a
terminal or non-terminal must occur in the input exactly once. The
operators modify this requirement:
?
*
+
*, but at least once (>= 1).
It is clear that `a*' is identical to `a+?', i.e., `zero or more times `a'' is equal to `optionally once or more often `a''.
The next line in the ex1 example defines the rule for expr:
expr: '(' expr* ')';
Thus, an expr is an opening parenthesis ((), followed by
zero or more exprs, followed by the closing parenthesis
()). The juxtaposition of the elements signify the implicit
concatenation operator.
Now all non-terminals have been defined, our grammar is complete. An example of using this parser by running `ex1' (each input line is followed by a ^D to indicate end of file):
$ ./ex1 () $ ./ex1 ) stdin:1: error at ')' $ ./ex1 ( stdin:1: error at EOF, expected token ')' $
Go to the first, previous, next, last section, table of contents.