4 Creating Input Language Analyzers and Parsers
If
a program needs to receive and process input, there must be a means of analyzing
the input before it is processed.
You can analyze input with one or more
routines within the program, or with a separate program designed to filter
the input before passing it to the main program.
The complexity of the input
interface depends on the complexity of the input; complicated input can require
significant code to parse it (break it into pieces that are meaningful to
the program).
This chapter describes the following two tools that help develop input
interfaces:
The
lex
tool uses a set of rules to generate
a program, called a
lexical analyzer, which analyzes
input and breaks it into categories, such as numbers, letters, or operators.
The
yacc
tool uses a set of rules to generate
a program, called a
parser, which analyzes input using
the categories identified by the lexical analyzer and determines what to do
with the input.
The
yacc
tool generates left-associative,
left-recursive (LALR) parsers.
For further information about LALR grammars,
refer to a compiler book such as
Compilers: Principles, Techniques, and Tools, by Alfred Aho, Ravi Sethi, and Jeffrey Ullman.
[Footnote 7]
To avoid confusion between the
lex
and
yacc
programs and the programs they generate,
lex
and
yacc
are referred to throughout this chapter as tools.
The following sections explain the two tools:
4.1 How the Lexical Analyzer Works
The lexical analyzer that
lex
generates
is a
deterministic finite-state automaton.
This design provides for
a limited number of states that the lexical analyzer can exist in, along with
the rules that determine what state the lexical analyzer moves to upon reading
and interpreting the next input character.
The compiled lexical analyzer performs the following functions:
Reads an input stream of characters.
Copies the input stream to an output stream.
Breaks the input stream into smaller strings that match the
regular expressions in the
lex
specification file.
Executes
an action for each regular expression that it recognizes.
Actions are C language
program fragments in the
lex
specification file.
An action
fragment does not have to be complete within itself; it can call subroutines
or other actions.
Figure 4-1
illustrates a simple lexical analyzer that
has three states:
start,
good, and
bad.
The program reads an input stream of characters.
It begins
in the
start
condition.
When it receives the first character,
the program compares the character with the rule.
If the character is alphabetic
(according to the rule), the program changes to the
good
state; if it is not alphabetic, the program changes to the
bad
state.
The program stays in the
good
state until it finds
a character that does not match its conditions, and then it moves to the
bad
state, which terminates the program.
Figure 4-1: Simple Finite State Model
The automaton allows the generated
lexical analyzer to look ahead more than one or two characters in an input
stream.
For example, suppose the
lex
specification file defines a rule that
looks for the string, ab, and another rule that looks for the string, abcdefg.
If the lexical analyzer gets an input string of abcdefh, it reads enough
characters to attempt a match on abcdefg.
When the h disqualifies a match
on abcdefg, the analyzer returns to the rule that looks for ab.
The first
two characters of the input match ab, so the analyzer performs any action
specified in that rule and then begins trying to find another match using
the remaining input, cdefh.
4.2 Writing a Lexical Analyzer Program with lex
The
lex
tool helps write a C language lexical analyzer
program that can receive character stream input and translate that input into
program actions.
To use
lex, you must write a specification
file that contains the following parts:
Regular expressions - Character patterns that the generated
lexical analyzer will recognize
Action
statements - C language program fragments that define how the generated
lexical analyzer is to react to regular expressions that it recognizes
The actual format and logic allowed in the specification file are discussed
in
Section 4.3.
The
lex
tool uses the information in the specification
file to generate the lexical analyzer.
The tool names the created analyzer
program
yy.lex.c.
The
yy.lex.c
program contains a set of standard functions together with the
analysis code that is generated from the specification file.
The analysis
code is contained in the
yylex
function.
Lexical analyzers
created by
lex
recognize simple grammar structures and
regular expressions.
You can compile a simple
lex
analyzer
program with the following command:
% cc -ll yy.lex.c
The
-ll
option tells the compiler to use the
lex
function
library.
This command yields an executable lexical analyzer.
If your program
uses complex grammar rules, or if it uses no grammar rules, you should create
a parser (by combining the
lex
and
yacc
tools) to ensure proper handling of the input.
(See
Section 4.6.)
The
yy.lex.c
output file can be moved to any other
system having a C compiler that supports the
lex
library
functions.
4.3 The lex Specification File
The format of
the
lex
specification file is as follows:
[ { definitions } ]
%%
[ { rules } ]
[ %%
{ user subroutines } ]
Except for the first pair of percent signs ( %% ),
which mark the beginning of the rules, all parts of the specification file
are optional.
The minimum
lex
specification file contains
no definitions, no rules, and no user subroutines.
Without a specified action for a pattern
match, the lexical analyzer copies the input pattern to the output without
changing it.
Therefore, this minimum specification file produces a lexical
analyzer that copies all input to the output unchanged.
This section contains the following information:
4.3.1 Defining Substitution Strings
You can define string macros before
the first pair of percent signs in the
lex
specification
file.
The
lex
tool expands these macros when it generates
the lexical analyzer.
Any line in this section that begins in column 1 and
that does not lie between
%{
and
%}
delimiters defines a
lex
substitution string.
Substitution string definitions have the
following general format:
name translation
The
name
and
translation
elements are separated by at least one blank or tab, and
name
begins with a letter.
When
lex
finds the
string
name
enclosed
in braces
( { } )
in the rules part of the specification file, it changes
name
to the string defined in
translation
and deletes the braces.
For example, to define the names
D
and
E, place the following definitions before the first
%%
delimiter in the specification file:
D [0-9]
E [DEde][-+]{D}+
These definitions can be used
in the rules section to make identification of integers and real numbers more
compact:
{D}+ printf("integer");
{D}+"."{D}*({E})?|
{D}*"."{D}+({E})?|
{D}+{E} printf("real");
You can also include the following
items in the definitions section:
Character set table (described in
Section 4.3.3)
List of start conditions (described in
Section 4.3.6)
Changes to size of arrays to accommodate larger source programs
4.3.2 Rules
The rules section of the specification
file contains control decisions that define the lexical analyzer that
lex
generates.
The rules are in the form of a two-column table.
The left column of the table contains regular expressions; the right column
of the table contains actions, one for each expression.
Actions
are C language
program fragments that can be as simple as a semicolon (the null statement)
or as complex as needed.
The lexical analyzer that
lex
creates contains both the expressions and the actions; when it finds a match
for one of the expressions, it executes the corresponding action.
For example, to create a lexical analyzer to look for the string, integer,
and print a message when the string is found, define the following rule:
integer printf ("found keyword integer");
This example uses the C language library function
printf
to print a message string.
The first blank or tab character in the rule indicates
the end of the regular expression.
When you use only one statement in an
action, put the statement on the same line and to the right of the expression
(integer
in this example).
When you use more than one
statement, or if the statement takes more than one line, enclose the action
in braces, as in a C language program.
For example:
integer {
printf ("found keyword integer");
hits++;
}
A lexical analyzer that changes some words in a file from British spellings
to the American spellings would have a specification file that contains rules
such as the following:
colour printf("color");
mechanise printf("mechanize");
petrol printf("gas");
This specification
file is not complete, however, because it changes the word petroleum to gaseum.
4.3.2.1 Regular Expressions
With
a few specialized additions,
lex
recognizes the standard
set of extended regular expressions described in
Chapter 1.
Table 4-1
lists the expression operators that are special to
lex.
Table 4-1: Regular Expression Operators for lex
| Operator |
Name |
Description |
{name} |
Braces |
When braces enclose a name, the name represents
a string defined earlier in the specification file.
For example,
{digit}
looks for a defined string named
digit
and inserts that string at the point in the expression where
{digit}
occurs.
Do not confuse this construct with an interval expression;
both are recognized by
lex. |
| " " |
Quotation marks |
Encloses literal strings to interpret as
text characters.
For example,
"$"
prevents
lex
from interpreting the dollar sign as an operator.
You can use
quotation marks for only part of a string; for example, both
"abc++"
and
abc"++"
match the literal string "abc++". |
/<b |
Slash |
Enables a match on the first expression (a) only if the second expression (b)
follows it immediately.
For example,
dog/cat
matches dog
if, and only if, cat immediately follows dog. |
<x> |
Angle brackets |
Encloses a start condition.
Executes the
associated action only if the lexical analyzer is in the indicated start condition
<x>.
If the condition
of being at the beginning of a line is start condition
ONE,
then the circumflex ( ^ ) operator would
be the same as the expression
<ONE>. |
| \n |
Newline character |
Do not use the actual newline character in
an expression.
Do not confuse the
\n
construct with the
\n
back-reference operator used in basic
regular expressions. |
| \t |
Tab |
Matches a literal tab character (09 hexadecimal)) |
| \b |
Backspace |
Matches a literal backspace (08 hexadecimal) |
| \\ |
Backslash |
Matches a literal backslash. |
| \digits |
Digits |
The character whose encoding is represented
by the three digit octal number. |
| \xdigits |
xDigits |
The character whose encoding is represented
by the hexadecimal integer. |
Usually, white
space (blanks or tabs) delimits the end of an expression and the start of
its associated action.
However, you can enclose blanks or tab characters
in quotation marks ( " " ) to include
them in an expression.
Use quotation marks around all blanks in expressions
that are not already within sets of brackets ( [ ] ).
4.3.2.2 Matching Rules
When more than
one expression in the rules section of a specification file can match the
current input, the lexical analyzer chooses which rule to apply using the
following criteria:
The longest matching string of characters
Among rules that match the same number of characters, the
rule that occurs first
For example, consider the following rules:
integer printf("found int keyword");
[a-z]+ printf("found identifier");
If the rules are given in this order and integers is the input word,
the analyzer calls the input an identifier because
[a-z]+
matches all eight characters of the word while
integer
matches only seven.
However, if the input is integer, both rules match.
In this case,
lex
selects the keyword rule because it occurs
first.
A shorter input, such as int, does not match the expression
integer, so
lex
selects the identifier rule.
4.3.2.2.1 Using Wildcard Characters to Match a String
Because the lexical analyzer chooses the longest match
first, you must be careful not to use an expression that is too powerful for
your intended purpose.
For example, a period followed by an asterisk and
enclosed in apostrophes ( '.*' ) might seem
like a good way to recognize any string enclosed in apostrophes.
However,
the analyzer reads far ahead, looking for a distant apostrophe to complete
the longest possible match.
Consider the following text:
'first' quoted string here, 'second' here
Given
this input, the analyzer will match on the following string:
'first' quoted string here, 'second'
Because the
period operator does not match a newline character, errors of this type are
usually not far reaching.
Expressions like
.*
stop on
the current line.
Do not try to defeat this action with expressions like
the following:
[.\n]+
Given this
expression, the lexical analyzer tries to read the entire input file, and
an internal buffer overflow occurs.
The following rule finds the smaller quoted strings `first' and `second'
from the preceding text example:
'[^'\n]*'"
This rule stops after matching `first' because it looks for an apostrophe
followed by any number of characters except another apostrophe or a newline
character, then followed by a second apostrophe.
The analyzer then begins
again to search for an appropriate expression, and it will find `second' as
it should.
This expression also matches an empty quoted string ( ' ' ).
4.3.2.2.2 Finding Strings Within Strings
Usually, the lexical analyzer program partitions the
input stream.
It does not search for all possible matches of each expression.
Each character is accounted for exactly once.
For example, to count occurrences
of both `she' and `he' in an input text, consider the following rules:
she s++;
he h++;
\n ;
. ;
The last two rules ignore everything other than
the two strings of interest.
However, because `she' includes `he', the analyzer
does not recognize the instances of `he' that are included within `she'.
A special action,
REJECT, is provided
to override this behavior.
This directive tells the analyzer to execute the
rule that contains it and then, before executing the next rule, restore the
position of the input pointer to where it was before the first rule was executed.
For example, to count the instances of `he' that are included within `she',
use the following rules:
she {s++; REJECT;}
he {h++; REJECT;}
\n ;
. ;
After counting an occurrence of `she', the analyzer
rejects the input stream and then counts the included occurrence of `he'.
In this example, `she' includes `he' but the reverse is not true, and you
can omit the
REJECT
action on `he'.
In other cases, such
as when a wildcard regular expression is being matched, determining which
input characters are in both classes can be difficult.
In general,
REJECT
is useful whenever the purpose
is not to partition the input stream but rather to detect all examples of
some items in the input where the instances of these items can overlap or
include each other.
4.3.2.3 Actions
When the lexical
analyzer matches one of the expressions in the rules section of the specification
file, it executes the action that corresponds to the expression.
Without
rules to match all strings in the input stream, the lexical analyzer copies
the input to standard output.
Therefore, do not create a rule that only copies
the input to the output.
Use this default output to find conditions not covered
by the rules.
When you
use a
lex-generated analyzer to process input for a parser
that
yacc
produces, provide rules to match all input strings.
Those rules must generate output that
yacc
can interpret.
For information on using
lex
with
yacc,
see
Section 4.5.
4.3.2.3.1 Null Action
To ignore the input associated with an
expression, use a semicolon ( ; ), the C
language null statement, as an action.
For example:
[ \t\n] ;
This rule ignores the three spacing characters
(blank, tab, and newline character).
4.3.2.3.2 Using the Same Action for Multiple Expressions
To
use the same action for several different expressions, create a series of
rules (one for each expression except the last) whose actions consist of only
a vertical bar character
( | ).
For the last expression, specify the action as you would
usually specify it.
The vertical bar character indicates that the action
for the rule containing it is the same as the action for the next rule.
For
example, to ignore blank, tab, and newline characters (shown in
Section 4.3.2.3.1),
you could use the following set of rules:
" " |
"\t" |
"\n" ;
The quotation marks around the special character
sequences (\n
and
\t) in this example
are not mandatory.
4.3.2.3.3 Printing a Matched String
To find out what text matched an expression in the rules section
of the specification file, include a C language
printf
function as one of the actions for that expression.
When the lexical analyzer
finds a match in the input stream, the program puts that matched string in
an external character array, called
yytext.
To print the matched string, use a rule like the following:
[a-z]+ printf("%s", yytext);
Printing the output in this way is common.
You can define an expression
like this
printf
statement as a macro in the definitions
section of the specification file.
If this action is defined as
ECHO, then the rules section entry looks like the following:
[a-z]+ ECHO;
See
Section 4.3.1
for information on defining macros.
4.3.2.3.4 Finding the Length of a Matched String
To
find the number of characters that the lexical analyzer matched for a particular
expression, use the external variable
yyleng.
For example,
the following rule counts both the number of words and the number of characters
in words in the input:
[a-zA-Z]+ {words++; chars += yyleng;}
This action totals the number of characters in the words
matched and assigns that value to the
chars
variable.
The following expression finds the last character in the string matched:
yytext[yyleng-1]
4.3.2.3.5 Getting More Input
The lexical analyzer
can run out of input before it completely matches an expression in a rules
file.
In this case, include a call to the
lex
function
yymore
in the action for that rule.
Usually, the next string from
the input stream overwrites the current entry in
yytext.
The
yymore
action appends the next string from the input
stream to the end of the current entry in
yytext.
For example,
consider a language that includes the following syntax:
A string is any set of characters between quotation marks
( " " ).
A backslash ( \ ) escapes
the next character to make that character part of the string.
For example,
the combination of a backslash and a quotation mark ( \ )
indicates that the quotation mark is part of the string instead of being the
closing delimiter for the string.
The following rule processes these lexical characteristics:
\"[^"]* {
if (yytext[yyleng-l] == '\\')
yymore();
else
... normal user processing
}
When this lexical analyzer receives a string such
as "abc\"def" (with the quotation marks exactly as shown), it first matches
the first five characters, "abc\.
The backslash causes a call to
yymore
to add the next part of the string, "def, to the end.
The
part of the action code labeled "normal user processing" must
process the quotation mark that ends the string.
4.3.2.3.6 Returning Characters to the Input
In some cases the lexical analyzer does not need all of the characters
that are matched by the currently successful regular expression; or it might
need to return matched characters to the input stream to be checked again
for another match.
To return characters to the input stream, use the
yyless(n)
call, where
n
is the number of characters of the current string that you want to keep.
Characters beyond the
nth character in the stream
are returned to the input stream.
This function provides the same type of
look-ahead that the slash operator ( / )
uses, but
yyless
allows more control over the look-ahead.
Using
yyless(0)
is equivalent to using
REJECT.
Use the
yyless
function to process text more than
once.
For example, a C language expression such as
x=-a
is ambiguous.
It could mean
x = -a, or it could
be an obsolete representation of
x -= a, which
is evaluated as
x = x - a.
To
treat this ambiguous expression as
x = -a
and
print a warning message, use a rule such as the following:
=-[a-zA-Z] {
printf("Operator (=-) ambiguous\n");
yyless(yyleng-1);
... action for =-...
}
4.3.3 Using or Overriding Standard Input/Output Routines
The
lex
program provides a set of input/output
(I/O) routines for the lexical analyzer to use.
Include calls to the following
routines in the C code fragments in your specification file:
input
- Returns the next input character
output(c)
- Writes the character
c
on the
output
unput(c)
- Pushes the character
c
back
onto the input stream to be read later by
input
These routines
are provided as macro definitions.
You can override them by writing your
own code for routines of the same names in the user subroutines section.
These
routines define the relationship between external files and internal characters.
If you change them, change them all in the same way.
They should follow
these rules:
If you write your own code, you must undefine these macros in the definitions
section of the specification file before the code for your own definitions:
%{
#undef input
#undef unput
#undef output
}%
Note
Changing the relationship of
unput
to
input
causes the look-ahead functions not to work.
When you are using a
lex-generated lexical analyzer
as a simple transformer/recognizer for piping from standard input to standard
output, you can avoid writing the framework by using the
lex
library (libl.a).
This library contains the
main
routine, which calls the
yylex
function for
you.
The standard
lex
library lets the lexical analyzer
back up a maximum of 100 characters.
If you need to be able
to read an input file containing the
NUL
character (00
hexadecimal), you must create a different version of the
input
routine.
The standard version of
input
returns a value
of 0 when reading a null, and the analyzer interprets this value as indicating
the end of the file.
The lexical analyzers that
lex
generates process
character I/O through the
input,
output,
and
unput
routines.
Therefore, to return values in
yytext, the analyzer uses the character representation that these
routines use.
Internally, however, each character is represented with a small
integer.
With the standard library, this integer is the value of the bit
pattern that the computer uses to represent the character.
Usually, the letter ,a, is represented in the same form as the character
constant
a.
If you change this interpretation with different
I/O routines, you must include a translation table in the definitions section
of the specification file.
The translation table begins and ends with lines
that contain only the
%T
keyword, and it contains lines
of the following form:
[{integer } {characterstring }]
The following example shows table entries that associate the
letter ,A, and the digit ,0, (zero) with their standard values:
%T
{65} {A}
{48} {0}
%T
4.3.4 End-of-File Processing
When the
lexical analyzer reaches the end of a file, it calls a library routine named
yywrap.
This routine returns a value of 1 to indicate to the lexical
analyzer that it should continue with normal wrap-up (operations associated
with the end of processing).
However, if the analyzer receives input from
more than one source, you must change the
yywrap
function.
The new function must get the new input and return a value of 0 to the lexical
analyzer.
A return value of 0 indicates that the program should continue
processing.
Multiple files specified on the command line are treated as a single
input file for the purpose of end-of-file handling.
You can also include code to print summary reports and tables in a special
version of
yywrap.
The
yywrap
function
is the only way to force
yylex
to recognize the end of
the input.
4.3.5 Passing Code to the Generated Program
You can define
variables in either the definitions section or the rules section of the specification
file.
When you process a specification file,
lex
changes
statements in the file into a lexical analyzer.
Any line in the specification
file that
lex
cannot interpret is passed unchanged to the
lexical analyzer.
The following four types of entries can be passed to the
lexical analyzer in this manner:
Lines beginning with a blank or tab that are not a part of
a
lex
rule are copied into the lexical analyzer.
If this
entry occurs before the first pair of percent signs ( %% )
in the specification file, the entry is external to any function in the code.
If the entry occurs after the first
%%,
it must be a C language program fragment that defines a variable.
You must define these statements before the first
lex
rule
in the specification file.
Lines beginning with a blank or tab that are program comments
are included as comments in the generated lexical analyzer.
The comments
must be in the C language format for comments.
Any lines that lie between lines containing only
%{
and
%}
are
copied to the lexical analyzer.
The symbols
%{
and
%}
are not copied.
Use this format to enter preprocessor statements
that must begin in column 1, or to copy lines that do not look like program
statements.
Any lines occurring after the third
%%
delimiter are copied to the lexical analyzer without format restrictions.
4.3.6 Start Conditions
Any rule can be associated with
a start condition; the lexical analyzer recognizes that rule only when the
analyzer is in that start condition.
You can change the current start condition
at any time.
You define start conditions in the definitions section of the specification
file by using a line with the following format:
% Start
[name1]
[
[name2 ...]
]
The
name1
and
name2
symbols represent conditions.
There is no limit to the number
of conditions, and they can appear in any order.
You can abbreviate
Start
to either
S
or
s.
Start-condition
names cannot be reserved words in C, nor can they be declared as the names
of variables, fields, and so on.
When using a start condition in the rules section of the specification
file, enclose the name of the start condition in angle brackets ( < > ) at the beginning of the rule.
The following
format defines a rule with a start condition:
[<name1]
[
[,name2 ...]
]
[> expression]
The lexical analyzer recognizes
expression
only when the analyzer is in the condition corresponding to one of the names.
To put
lex
in a particular
start condition, execute the following action statement (in the action part
of a rule):
BEGIN name;
This statement changes the start
condition to
name.
To resume the normal state,
use the following action:
BEGIN 0;
As shown in the preceding syntax diagram, a rule can be active in several
start conditions.
For example:
<start1,start2,start3> [0-9]+ printf("integer");
This rule prints integer only if it finds an integer while
in one of the three named start conditions.
Any rule that does not begin
with a start condition is always active.
4.4 Generating a Lexical Analyzer
Generating a
lex-based lexical analyzer program is a two-step process, as follows:
Run
lex
to change the specification file
into a C language program.
The resulting program is in a file named
lex.yy.c.
Process
lex.yy.c
with the
cc -ll
command to compile the program and link it with a library of
lex
subroutines.
The resulting executable program is named
a.out.
For example, if the
lex
specification file is called
lextest, enter the following commands:
% lex lextest
% cc lex.yy.c -ll
Although the default
lex
I/O routines use the C language
standard library, the lexical analyzers that
lex
generates
do not require them.
You can include different copies of the
input,
output, and
unput
routines
to avoid using those in the library.
(See
Section 4.3.3.)
Table 4-2
describes the options for the
lex
command.
Table 4-2: Options for the lex Command
| Option |
Description |
-n |
Suppresses the statistics summary that is
produced by default when you set your own table sizes for the finite state
machine.
See the
lex(1)
reference page for information about specifying
the state machine. |
-t |
Writes the generated lexical analyzer code
to standard output instead of to the
lex.yy.c
file. |
-v |
Provides a one-line summary of the general
finite state machine statistics. |
Because
lex
uses fixed names for intermediate and output files, you can
have only one
lex-generated program
in a given directory unless you use the
-t
option
to specify an alternative file name.
4.5 Using lex with yacc
When
used alone, the
lex
tool creates a lexical analyzer that
recognizes simple one-word input or receives statistical input.
You can also
use
lex
with a parser generator, such as
yacc.
The
yacc
tool generates a program, called a
parser, that analyzes the construction of multiple-word input.
This parser
program operates well with lexical analyzers that
lex
generates;
these lexical analyzers recognize only regular expressions and format them
into character packages called
tokens.
A token
is
the smallest independent unit of meaning as defined by either the parser or
the lexical analyzer.
A token can contain data, a language keyword, an identifier,
or other parts of a language syntax.
A token can be any string of characters;
it can be part or all of a word or series of words.
The
yacc
tool produces parsers that recognize many types of grammar with no regard
to context.
These parsers need a preprocessor, such as a
lex-generated
lexical analyzer, to recognize input tokens.
When a
lex-generated lexical analyzer is used as
the preprocessor for a
yacc-generated
parser, the lexical analyzer partitions the input stream.
The
parser assigns structure to the resulting pieces.
Figure 4-2
shows how
lex
and
yacc
generate programs
and how the programs work together.
You can also use other programs along
with those generated by
lex
or
yacc.
Figure 4-2: Producing an Input Parser with lex and yacc
The parser program requires that its preprocessor (the lexical analysis
function) be named
yylex.
This is the name
lex
gives to the analysis code in a lexical analyzer it generates.
If a lexical analyzer is used by itself, the default
main
program in the
lex
library calls the
yylex
routine, but if a
yacc-generated parser is loaded and its
main
program
is used, the parser calls
yylex.
In this case, each
lex
rule
should end with the following line, where the appropriate token value is returned:
return(token);
To find the names for tokens that
yacc
uses, compile the lexical analyzer (the
lex
output file)
as part of the parser (the
yacc
output file) by placing
the following line in the last section of the
yacc
grammar
file:
#include lex.yy.c
Alternatively,
you can include the
yacc
output (the
y.tab.h
file) into your
lex
program specification file, and use
the token names that
y.tab.h
defines.
For example, if
the grammar file is named
good
and the specification file
is named
better, the following command sequence creates
the final program:
% yacc good
% lex better
% cc y.tab.c -ly -ll
To get a
main
program that invokes the
yacc
parser, load the
yacc
library (-ly
in the preceding example) before the
lex
library.
You
can generate
lex
and
yacc
programs in
either order.
4.6 Creating a Parser with yacc
To generate a parser with
yacc, you must write
a grammar file that describes the input data stream and what the parser is
to do with the data.
The grammar file includes rules describing the input
structure, code to be invoked when these rules are recognized, and a routine
to do the basic input.
The
yacc
tool uses the information in the grammar
file to generate
yyparse, a program that controls the input
process.
This is the parser that calls the
yylex
input routine (the lexical analyzer) to pick up tokens from
the input stream.
The parser organizes these tokens according to the structure
rules in the grammar file.
The structure rules are called grammar rules.
When the parser recognizes a grammar rule, it executes the user code (action)
supplied for that rule.
Actions return values and use
the values returned by other actions.
In addition to the specifications that
yacc
recognizes
and uses, the grammar file can also contain the following functions:
main
-
A C language function that contains, as a minimum, a call to the
yyparse
function, which
yacc
generates.
A limited
form of this function is in the
yacc
library.
yyerror
-
A C language function to handle errors that can occur during parser operation.
A limited form of this function is in the
yacc
library.
yylex
- A C
language function to perform lexical analysis on the input stream and pass
tokens (with values, if required) to the parser.
The function must return
an integer that represents the kind of token that was read.
The integer is
called the token number.
In addition, if a value is associated with the token,
the lexical analyzer must assign that value to the external variable
yylval.
See
Section 4.7.1.3
for more information on token numbers.
To build
a lexical analyzer that works well with the parser that
yacc
generates, use the
lex
tool (see
Section 4.3).
The
yacc
tool processes a grammar file to generate
a file of C language functions and data, named
y.tab.c.
When compiled
using the
cc
command, these functions form a combined function
named
yyparse.
This
yyparse
function calls
yylex, the lexical analyzer, to get input tokens.
The analyzer continues providing input until the parser detects an error
or the analyzer
returns
an
endmarker
token to indicate the end of the operation.
If an error occurs and
yyparse
cannot recover,
yyparse
returns a value of 1 to the
main
function.
If it finds the
endmarker
token,
yyparse
returns a value of 0 to
main.
Use the C programming language to write the action code and other subroutines.
The
yacc
program uses many of the C language syntax conventions
for the grammar file.
4.6.1 The main and yyerror Functions
You must provide
function routines named
main
and
yyerror
in the grammar file.
To ease the initial effort of using
yacc,
the
yacc
library provides simple versions of the
main
and
yyerror
routines.
You can include these
routines by using the
-ly
option to the loader or the
cc
command.
The source code
for the
main
library function is as follows:
main()
{
yyparse();
}
The source code for the
yyerror
library
function follows:
#include <stdio.h>
void yyerror(s)
char *s;
{
fprintf( stderr, " %s\n" ,s);
}
The argument to
yyerror
is a string
containing an error message, usually the string syntax error.
These are very limited programs.
You should provide more sophistication
in these routines, such as keeping track of the input line number and printing
it along with the message when a syntax error is detected.
You can use the
value of the external integer variable
yychar.
This
variable contains the look-ahead token number at the time the error was detected.
4.6.2 The yylex Function
The
yylex
program input
routine that you supply must be able to do the following:
A token is a symbol or name that tells
yyparse
which
pattern is being sent to it by the input routine.
A symbol can be in one
of the following two classes:
Terminal symbols - Values returned by
yylex
to represent the primitive building blocks of the grammar,
as bricks are the primitive elements of a wall.
Nonterminal symbols - The composite symbols
that are used by the
yacc
grammar to describe more complex
orderings or aggregations of the terminal symbols, as a wall is an assembly
of bricks.
For example, if the lexical analyzer recognizes any numbers, names,
and operators, these elements are taken to be terminal symbols.
Nonterminal
symbols that the
yacc
grammar recognizes are elements like
EXPR,
TERM, and
FACTOR.
Suppose
the input routine separates an input stream into the tokens of
WORD,
NUMBER, and
PUNCTUATION.
Consider the input sentence "I have 9 turkeys." The analyzer
could pass the following strings and tokens to the parser:
| String |
Token |
| I |
WORD |
| have |
WORD |
| 9 |
NUMBER |
| turkeys |
WORD |
| . |
PUNCTUATION |
The
yyparse
function must contain
definitions for the tokens that the input routine passes to it.
The
yacc
command's
-d
option causes the program
to generate a list of tokens in a file named
y.tab.h.
This list is a set of
#define
statements that let
yylex
use the same tokens as the parser.
To avoid conflict with the parser, do not use names that begin with
the letters
yy.
You can use
lex
to generate
the input routine, or you can write it in the C language.
See
Section 4.3
for information about using
lex.
4.7 The Grammar File
A
yacc
grammar
file consists of the following three sections:
Declarations
Rules
Programs
Two percent signs
( %% ) that appear together separate the sections of the grammar
file.
To make the file easier to read, put the percent signs on a line by
themselves.
A grammar file has the following format:
[ declarations ]
%%
rules
[ %%
programs ]
Except
for the first pair of percent signs ( %% ),
which mark the beginning of the rules, and the rules themselves, all parts
of the grammar file are optional.
The minimum
yacc
grammar
file contains no definitions and no programs, as follows:
%%
rules
Except within names or reserved
symbols, the
yacc
program ignores blanks, tabs, and newline
characters in the grammar file.
You can use these characters to make the
grammar file easier to read.
Do not use blanks, tabs, or newline characters
in names or reserved symbols.
4.7.1 Declarations
The declarations section
of the
yacc
grammar file contains the following elements:
Declarations for any variables or constants used in other
parts of the grammar file
The
#include
statements to call in other
files as part of this file (used for library header files)
Statements that define processing conditions for the generated
parser
Declarations for variables or constants
conform to the syntax of the C programming language, as follows:
type-specifier declarator;
In
this syntax,
type-specifier
is a data type keyword
and
declarator
is the name of the variable or constant.
Names can be any length and can consist of letters, dots, underscores, and
digits.
A name cannot begin with a digit.
Uppercase and lowercase letters
are distinct.
The names used in the body of a grammar rule can represent
tokens or nonterminal symbols.
If
you do not declare a name in the declarations section, you can use that name
only as a nonterminal symbol.
Define each nonterminal symbol by using it
as the left side of at least one rule in the rules section.
The
#include
statements are identical to C language syntax and perform
the same function.
The
yacc
tool has a set of keywords, listed in
Table 4-3, that define processing conditions for the generated
parser.
Each of the keywords begins with a percent sign
( % )
and is followed by a list of tokens.
Table 4-3: Processing-Condition Definition Keywords in yacc
| Keyword |
description |
%left |
Identifies tokens that are left-associative
with other tokens. |
%nonassoc |
Identifies tokens that are not associative
with other tokens. |
%right |
Identifies tokens that are right-associative
with other tokens. |
%start |
Identifies a name for the start symbol. |
%token |
Identifies the token names that
yacc
accepts.
Declare all token names in the declarations section. |
All tokens listed on the same
line have the same precedence level and association; lines appear in the file
in order of increasing precedence or binding strength.
For example:
%left '+' '-'
%left '*' '/'
This example describes the precedence
and associativity of the four arithmetic operators.
The addition ( + ) and subtraction ( - )
operators are left-associative and have lower precedence than the multiplication
( * ) and division ( / )
operators, which are also left-associative.
4.7.1.1 Defining Global Variables
You can define global variables to be used by some or all parser
actions, as well as by the lexical analyzer, by enclosing the declarations
for those variables in matched pairs of symbols consisting of a percent sign
and a brace
(%{
and
%}).
For example, to make the
var
variable available to all parts of the complete program, place
the following entry in the declarations section of the grammar file:
%{ int var = 0; %}
4.7.1.2 Start Symbols
The parser recognizes a special symbol called the start symbol.
The start symbol is the name assigned to the grammar rule that describes
the most general structure of the language to be parsed.
Because it is the
most general structure, it is the structure where the parser starts in its
top-down analysis of the input stream.
You declare the start symbol in the
declarations section by using the
%start
keyword.
If you
do not declare a start symbol, the parser uses the name of the first grammar
rule in the file.
For example, in parsing a C language procedure, the following is the
most general structure for the parser to recognize:
main()
{
code_segment
}
The start symbol should point to the rule that describes
this structure.
All remaining rules in the file describe ways to identify
lower-level structures within the procedure.
4.7.1.3 Token Numbers
Token numbers are nonnegative integers
that represent the names of tokens.
Because the lexical analyzer passes the
token number to the parser instead of the actual token name, the programs
must assign the same numbers to the tokens.
You can assign numbers to the tokens used in the
yacc
grammar file.
If you do not assign numbers to the tokens,
yacc
assigns numbers using the following rules:
Note
Do not assign a token
number of 0 (zero).
This number is assigned to the
endmarker
token.
You cannot redefine it.
To assign a number to a token (including literals) in the declarations
section of the grammar file, put a nonzero positive integer immediately after
the token name in the
%token
line.
This integer is the
token number of the name or literal.
Each number must be unique.
Any lexical
analyzer used with
yacc
must return either 0 (zero) or
a negative value for a token when the end of the input is reached.
4.7.2 Grammar Rules
The rules section of the
yacc
grammar file contains one or more grammar rules.
Each rule
describes a structure and gives it a name.
A grammar rule has the following
format:
[nonterminal-name : BODY ;]
In this syntax,
BODY
is a sequence
of zero or more names and literals.
The colon and the
semicolon are required
yacc
punctuation.
If there are several grammar rules with the same nonterminal name, use
the vertical bar
( | ) to avoid rewriting the left side.
In addition, use the
semicolon ( ; ) only at the end of all rules
joined by vertical bars.
The two following sets of grammar rules are equivalent:
Set 1
A : B C D ;
A : E F ;
A : G ;
Set 2
A : B C D
| E F
| G
;
4.7.2.1 Null String
To indicate a nonterminal symbol that
matches the null string, use a semicolon by itself in the body of the rule,
as follows:
nullstr : ;
4.7.2.2 End-of-Input Marker
When the lexical analyzer reaches the end of the input stream,
it sends a special token, called
endmarker, to the parser.
This token signals the end of the input and has a token value of 0.
When
the parser receives an
endmarker
token, it checks to see
that it has assigned all of the input to defined grammar rules and that the
processed input forms a complete unit (as defined in the
yacc
grammar file).
If the input is a complete unit, the parser stops.
If the
input is not a complete unit, the parser signals an error and stops.
The lexical analyzer must send the
endmarker
token
at the correct time, such as the end of a file, or the end of a record.
4.7.2.3 Actions in yacc Parsers
With each grammar rule, you can specify
actions to be performed each time the parser recognizes the rule in the input
stream.
Actions return values and obtain the values returned by previous
actions.
The lexical analyzer can also return values for tokens.
An action is a C language statement that does input and output, calls
subprograms, and alters external vectors and variables.
You specify an action
in the grammar file with one or more statements enclosed in braces ( { } ).
For example, the following are grammar rules
with actions:
A : '('B')'
{
hello(1, "abc" );
};
XXX : YYY ZZZ
{
printf("a message\n");
flag = 25;
}
An action can receive values generated by other actions
by using numbered
yacc
parameter
keywords ($1,
$2, and so on).
These
keywords refer to the values returned by the components of the right side
of a rule, reading from left to right.
For example:
A : B C D ;
When this code is executed,
$1
has the value returned by the rule that recognized
B,
$2
the value returned by the rule that recognized
C,
and
$3
the value returned by the rule that recognized
D.
To return a value, the action sets the pseudovariable
$$
to some value.
For example, the following action returns a value of 1:
{ $$ = 1;}
By
default, the value of a rule is the value of the first element in it ( $1 ).
Therefore, you do not need to provide actions for rules
that have the following form:
A : B ;
To get control of the parsing
process before a rule is completed, write an action in the middle of a rule.
If this rule returns a value through the
$n
parameters, actions that come after it can use that value.
The action can use values returned by actions that come before it.
Therefore,
the following rule sets
x
to 1 and
y
to the value returned by
C:
A : B
{
$$ =1;
}
C
{
x = $2;
y = $3;
}
;
Internally,
yacc
creates
a new nonterminal symbol name for the action that occurs in the middle, and
it creates a new rule matching this name to the null string.
Therefore,
yacc
treats the preceding program as if it were written in the following
form, where
$ACT
is an empty action:
$ACT : /* null string */
{
$$ = 1;
}
;
A : B $ACT C
{
x = $2;
y = $3;
}
;
4.7.3 Programs
The programs section of
the
yacc
grammar file contains C language functions that
can be used by the actions in the rules section.
In addition, if you write
a lexical analyzer
(yylex, the input routine to the parser), include
it in the programs section.
4.7.4 Guidelines for Using Grammar Files
The following sections describe some general guidelines for using
yacc
grammar files.
They provide information on the following:
4.7.4.1 Using Comments
Comments in the grammar file explain what the program is doing.
You
can put comments anywhere in the grammar file that you can put a name.
However,
to make the file easier to read, put the comments on lines by themselves at
the beginning of functional blocks of rules.
Comments in a
yacc
grammar file have exactly the same form as comments in a C language
program; that is, they begin with a slash and an asterisk ( /* ) and end with an asterisk and a slash ( */ ).
For example:
/* This is a comment on a line by itself. */
4.7.4.2 Using Literal Strings
A literal string is one or more characters
enclosed in apostrophes, or single quotation marks ( ' ' ).
As in the C language, the backslash ( \ ) is an escape character within literals, and all the C
language special-character sequences are recognized, as follows:
\n |
Newline character |
\r |
Return |
\' |
Apostrophe, or single quote |
\\ |
Backslash |
\t |
Tab |
\b |
Backspace |
\f |
Form feed |
\nnn |
The value
nnn
in octal |
Never
use
\0
or
0
(the null character) in
grammar rules.
4.7.4.3 Guidelines for Formatting the Grammar File
The following guidelines will
help make the
yacc
grammar file more readable:
Use uppercase letters for token names and lowercase letters
for nonterminal symbol names.
Put grammar rules and actions on separate lines to allow for
changing either one without changing the other.
Put all rules with the same left side together.
Enter the
left side once and use vertical bars ( | )
to begin the rest of the rules for that left side.
For each set of rules with the same left side, enter the semicolon
( ; ) once on a line by itself following
the last rule for that left side.
You can then add new rules easily.
Indent rule bodies by two tab stops and action bodies by three
tab stops.
4.7.4.4 Using Recursion in a Grammar File
Recursion
is the process of using a function to define itself.
In language definitions,
these rules usually take the following form:
rule : end case
| rule, end case
The simplest case of
rule
is the end case, but
rule
can also be made up of more than one occurrence of
end case.
The entry in the second line that uses
rule
in the definition of
rule
is the instance of
recursion.
Given this rule, the parser cycles through the input until the
stream is reduced to the final end case.
The
yacc
tool supports left-recursive grammar, not
right-recursive.
When you use recursion in a rule, always put the call to
the name of the rule as the leftmost entry in the rule (as it is in the preceding
example).
If the call to the name of the rule occurs later in the line, as
in the following example, the parser can run out of internal stack space and
crash:
rule : end case
| end case, rule
4.7.4.5 Errors in the Grammar File
The
yacc
tool cannot produce
a parser for all sets of grammar specifications.
If the grammar rules contradict
themselves or require matching techniques different from those that
yacc
has,
yacc
will not produce a parser.
In
most cases,
yacc
provides messages to indicate the errors.
To correct these errors, redesign the rules in the grammar file or provide
a lexical analyzer to recognize the patterns that
yacc
cannot handle.
4.7.5 Error Handling by the Parser
When the parser reads an input stream, that input
stream can fail to match the rules in the grammar file.
If there is an error-handling
routine in the grammar file, the parser can allow for entering the data again,
skipping over the bad data, or for a cleanup and recovery action.
When the
parser finds an error, for example, it might need to reclaim parse tree storage,
delete or alter symbol table entries, and set switches to avoid generating
any further output.
When an error occurs, the parser stops unless you provide error-handling
routines.
To continue processing the input to find more errors, restart the
parser at a point in the input stream where the parser can try to recognize
more input.
One way to restart the parser when an error occurs is to discard
some of the tokens following the error, and try to restart the parser at that
point in the input stream.
The
yacc
tool has a special token name,
error, to use for error handling.
Put this
token in your grammar file at places where an input error might occur so that
you can provide a recovery routine.
If an input error occurs in a position
protected by the
error
token, the parser executes the action
for the
error
token rather than the normal action.
To prevent a single error from producing many error messages, the parser
remains in an error state until it successfully processes three tokens following
an error.
If another error occurs while the parser is in the error state,
the parser discards the input token and does not produce a message.
You can
also specify a point at which the parser should resume processing by providing
an argument to the
error
action.
For example:
stat : error ';'
This rule tells the parser
that, when there is an error, it should skip over the token and all following
tokens until it finds the next semicolon.
All tokens after the error and
before the next semicolon are discarded.
When the parser finds the semicolon,
it reduces this rule and performs any cleanup action associated with it.
4.7.5.1 Providing for Error Correcting
You can allow
the person entering the input stream in an interactive environment to correct
any input errors by reentering a line in the data stream.
For example:
input : error '\n'
{
printf(" Reenter last line: " );
}
input
{
$$ = $4;
}
;
In the previous example the parser stays in the
error state for three input tokens following the error.
If an error is encountered
in the first three tokens, the parser deletes the tokens and does not display
a message.
Use the
yyerrok;
statement for recovery.
When
the parser encounters the
yyerrok;
statement, it leaves
the error state and begins normal processing.
Following is the recovery example:
input : error '\n'
{
yyerrok;
printf( "Reenter last line: " );
}
input
{
$$ = $4
}
;
4.7.5.2 Clearing the Look-Ahead Token
The look-ahead token is the next token to
be examined by the parser.
When an error occurs, the look-ahead token becomes
the token at which the error was detected.
However, if the error recovery
action includes code to find the correct place to start processing again,
that code must also change the look-ahead token.
To clear the look-ahead
token, include the
yyclearin;
statement in the error recovery
action.
4.8 Parser Operation
The
yacc
program turns the grammar file into a C
language program that, when compiled and executed, parses the input according
to the grammar rules.
The parser is a finite state machine with a stack.
The parser can read and remember the next input token (the look-ahead token).
The current state is always the state that is on the top of the stack.
The
states of the finite state machine are represented by small integers.
Initially,
the machine is in state 0 (zero), the stack contains only 0 (zero), and no
look-ahead token has been read.
The machine can perform one of the following four actions:
shift
n |
The parser pushes the current state onto
the stack, makes
n
the current state, and clears
the look-ahead token. |
reduce
r |
The
r
argument
is a rule number.
When the parser finds a token sequence matching rule number
r
in the input stream, the parser replaces that sequence with the
rule number in the output stream. |
accept |
The parser has looked at all input, matched
it to the grammar specification, and recognized the input as satisfying the
highest level structure (defined by the start symbol).
This action appears
only when the look-ahead token is the end marker and indicates that the parser
has successfully done its job. |
error |
The parser cannot continue processing the
input stream and still successfully match it with any rule defined in the
grammar specification.
The input tokens it looked at, together with the look-ahead
token, cannot be followed by anything that would result in a legal input.
The parser reports an error and attempts to recover the situation and resume
parsing. |
The parser performs the following actions during one process step:
Based on its current state, the parser decides whether it
needs a look-ahead token to decide the action to take.
If it needs one and
does not have one, it calls
yylex
to obtain the next token.
Using the current state and the look-ahead token if needed,
the parser decides on its next action and carries it out.
This can result
in states being pushed onto the stack or popped off the stack and in the look-ahead
token being processed or left alone.
4.8.1 The shift Action
The
shift
action is the most common action
the parser takes.
Whenever the parser does a
shift, there
is always a look-ahead token.
Consider the following parser action rule:
IF shift 34
When the parser is in the state that
contains this rule and the look-ahead token is
IF, the
parser performs the following steps:
Pushes the current state down on the stack
Makes state 34 the current state (puts it on the top of the
stack)
Clears the look-ahead token
4.8.2 The reduce Action
The
reduce
action prevents the stack from growing
too large.
The parser uses reducing actions after it has matched the right
side of a rule with the input stream and is ready to replace the tokens in
the input stream with the left side of the rule.
The parser might have to
use the look-ahead token to decide if the pattern is a complete match.
Reducing actions are associated with individual grammar rules.
Because
grammar rules also have small integer numbers, you can easily confuse the
meanings of the numbers in the
shift
and
reduce
actions.
For example, the first of the two following actions refers
to grammar rule 18; the second refers to machine state 34:
reduce 18
IF shift 34
For example, consider reducing the following rule:
A : x y z ;
The parser pops off the top three states from
the stack.
The number of states popped equals the number of symbols on the
right side of the rule.
These states are the ones put on the stack while
recognizing
x,
y, and
z.
After popping these states, the parser uncovers the state the parser was in
before beginning to process the rule (the state that needed to recognize rule
A
to satisfy its rule).
Using this uncovered state and the symbol
on the left side of the rule, the parser performs a
goto
action, which is similar to a
shift
of
A.
A new state is obtained and pushed onto the stack, and parsing continues.
The
goto
action is different from an ordinary
shift
of a token.
The look-ahead token is cleared by a
shift
but is not affected by a
goto.
When the
three states are popped in this example, the uncovered state contains an entry
such as the following:
A goto 20
This entry causes state 20 to be pushed onto the stack and become the current
state.
The
reduce
action is also important in the treatment
of user-supplied actions and values.
When a rule is reduced, the parser executes
the code that you included in the rule before adjusting the stack.
In addition
to the stack holding the states, another stack running in parallel with it
holds the values returned from the lexical analyzer and the actions.
When
a
shift
takes place, the external variable
yylval
is
copied onto the value stack.
After executing the code that you provide, the
parser performs the reduction.
When the parser performs the
goto
action, it copies the external variable
yylval
onto
the value stack.
The
yacc
variables whose names begin
with a dollar sign ( $ ) refer to the value
stack.
4.8.3 Ambiguous Rules and Parser Conflicts
A
set of grammar rules is ambiguous if any possible input string can be structured
in two or more different ways.
For example:
expr : expr '-' expr
This rule forms an arithmetic expression by putting two
other expressions together with a minus sign between them, but this grammar
rule does not specify how to structure all complex inputs.
For example:
expr - expr - expr
Using the preceding rule, a
program could structure this input as either left-associative or right-associative:
( expr - expr ) - expr
or
expr - ( expr - expr )
These two forms produce
different results when evaluated.
When the parser tries to handle an ambiguous rule, it can become confused
over which of its four actions to perform when processing the input.
The
following two types of conflicts develop:
Shift/reduce
conflict |
A rule can be evaluated correctly using either
a
shift
action or a
reduce
action, with
different results. |
Reduce/reduce
conflict |
A rule can be evaluated correctly using one
of two different
reduce
actions, producing two different
actions. |
A
shift/shift
conflict is not possible.
These conflicts result when a rule is not as complete as it could be.
For example, consider the following input and the preceding ambiguous rule:
a - b - c
After reading the first three parts
of the input, the parser has the following:
a - b
This input matches the right side of the grammar rule.
The parser can reduce the input by applying this rule.
After applying the
rule, the input becomes the following:
expr
This is the left side of the rule.
The
parser then reads the final part of the input, as follows:
- c
The parser now has the following:
expr - c
Reducing this
input produces a left-associative interpretation.
However, the parser can also look ahead in the input stream.
If, after
receiving the first three parts of the input, it continues reading the input
stream until it has the next two parts, it then has the following input:
a - b - c
Applying the rule to the rightmost three
parts reduces
b - c
to
expr.
The parser then has the following:
a - expr
Reducing the expression once more produces
a right-associative interpretation.
Therefore, at the point where the parser has read the first three parts,
it can take one of two legal actions: a
shift
or a
reduce.
If the parser has no rule by which to decide between the
actions, a
shift/reduce
conflict results.
A similar situation occurs if the parser can choose between two valid
reduce
actions.
That situation is called a
reduce/reduce
conflict.
When
shift/reduce
or
reduce/reduce
conflicts occur,
yacc
produces a parser by selecting a
valid step wherever it has a choice.
If you do not provide a rule to make
the choice,
yacc
uses the following rules:
In a
shift/reduce
conflict, shift.
In a
reduce/reduce
conflict, reduce by
the grammar rule that can be applied at the earliest point in the input stream.
Using actions within rules can cause conflicts if the action must be
done before the parser can be sure which rule is being recognized.
In these
cases, using the preceding rules leads to an incorrect parser.
For this reason,
yacc
reports the number of
shift/reduce
and
reduce/reduce
conflicts that it has resolved by applying its rules.
4.9 Turning on Debug Mode
For normal operation, the external integer
variable
yydebug
is set to 0.
However, if you set it to
any nonzero value, the parser generates a running description of the input
tokens that it receives and the actions that it takes for each token.
You
can set the
yydebug
variable in one of the following two
ways:
Use the
yydebug
function by including the
following C language statement in the declarations section of the
yacc
grammar file:
yydebug = 1;
Use a debugger to execute the final parser, and set the
yydebug
variable on or off using debugger commands.
For further
details about using debuggers, such as
dbx, see the reference
pages for the various debuggers.
4.10 Creating a Simple Calculator Program
You
can use the programs for a
lex-generated lexical analyzer
and a
yacc-generated parser, shown in
Example 4-1
and
Example 4-2, to create a simple desk calculator program
that performs addition, subtraction, multiplication, and division operations.
The calculator program also lets you assign values to variables (each designated
by a single lowercase letter) and then use the variables in calculations.
The files that contain the programs are as follows:
calc.l
- The
lex
specification file that defines the lexical analysis rules
calc.y
- The
yacc
grammar file that defines the parsing rules, and calls the
yylex
function created by
lex
to provide input
By convention,
lex
and
yacc
programs
use the letters
.l
and
.y
respectively
as file name suffixes.
Example 4-1
and
Example 4-2
contain the program fragments exactly as they should be entered.
The following processing instructions assume that the files are in your
current directory; perform the steps in the order shown to create the calculator
program using
lex
and
yacc:
Process the
yacc
grammar file by using
the following command.
The
-d
option tells
yacc
to create a file that defines the tokens it uses in addition
to the C language source code.
% yacc -d calc.y
This command creates the following files:
Process the
lex
specification file by using
the following command:
% lex calc.l
This command creates the
lex.yy.c
file, containing the C language source file that
lex
created for the lexical analyzer.
Compile and link the two C language source files by using
the following command:
% cc -o calc y.tab.c lex.yy.c
Use the
ls
command to verify that the following
files were created:
y.tab.o
- The object file for
y.tab.c
lex.yy.o
- The object file for
lex.yy.c
calc
- The executable program file
You can run the program by entering the
calc
command.
You can then enter numbers and operators in algebraic fashion.
After you
press Return, the program displays the result of the operation.
You can assign
a value to a variable as follows:
m=4
You can use variables in calculations as follows:
m+5
9
4.10.1 Parser Source Code
Example 4-1
shows the contents of the
calc.y
file.
This file has entries in all three of the sections of a
yacc
grammar file: declarations, rules, and programs.
The grammar
defined by this file supports the usual algebraic hierarchy of operator precedence.
Descriptions of the various elements of the file and their functions
follow the example.
Example 4-1: Parser Source Code for a Calculator
%{
#include <stdio.h> [1]
int regs[26]; [2]
int base;
%}
%start list [3]
%token DIGIT LETTER [4]
%left '|' [5]
%left '&'
%left '+' '-'
%left '*' '/' '%'
%left UMINUS /*supplies precedence for unary minus */
%% /* beginning of rules section */
list: /*empty */
| list stat'\n'
| list error'\n'
{
yyerrok;
}
;
stat: expr
{
printf("%d\n",$1);
}
|
LETTER '=' expr
{
regs[$1] = $3;
}
;
expr: '(' expr ')'
{
$$ = $2;
}
|
expr '*' expr
{
$$ = $1 * $3;
}
|
expr '/' expr
{
$$ = $1 / $3;
}
|
expr '%' expr
{
$$ = $1 % $3;
}
|
expr '+' expr
{
$$ = $1 + $3;
}
|
expr '-' expr
{
$$ = $1 - $3;
}
|
expr '&' expr
{
$$ = $1 & $3;
}
|
expr '|' expr
{
$$ = $1 | $3;
}
|
'-' expr %prec UMINUS
{
$$ = -$2;
}
|
LETTER
{
$$ = regs[$1];
}
|
number
;
number: DIGIT
{
$$ = $1;
base = ($1==0) ? 8:10;
}
|
number DIGIT
{
$$ = base * $1 + $2;
}
;
%%
main()
{
return(yyparse());
}
yyerror(s)
char *s;
{
fprintf(stderr," %s\n",s);
}
yywrap()
{
return(1);
}
The declarations section contains entries that
perform the following functions:
Include standard I/O header file
[Return to example]
Define global variables
[Return to example]
Define the rule list as the place to start processing
[Return to example]
Define the tokens used by the parser
[Return to example]
Define the operators and their precedence
[Return to example]
The rules section defines the rules that parse the input stream.
The programs section contains the following routines.
Because these
routines are included in this file, you do not need to use the
yacc
library when processing this file.
main( )
- The required main program
that calls
yyparse( )
to start the program
yyerror(s)
- The error-handling routine,
which prints a syntax error message
yywrap( )
- The wrap-up routine that
returns a value of 1 when the end of input occurs
4.10.2 Lexical Analyzer Source Code
Example 4-2
shows the contents of the
calc.l
file.
This file contains
#include
statements
for standard input and output and for the
y.tab.h
file, which is
generated by
yacc
before you run
lex
on
calc.l.
The
y.tab.h
file defines
the tokens that the parser program uses.
Also,
calc.l
defines
the rules to generate the tokens from the input stream.
Example 4-2: Lexical Analyzer Source Code for a Calculator
%{
#include <stdio.h>
#include "y.tab.h"
int c;
extern int yylval;
%}
%%
" " ;
[a-z] {
c = yytext[0];
yylval = c - 'a';
return(LETTER);
}
[0-9] {
c = yytext[0];
yylval = c - '0';
return(DIGIT);
}
[^a-z0-9\b] {
c = yytext[0];
return(c);
}