DANTE - A Recursive Descent Compiler Tool

John W. Jordan

April 23, 2006

© 2006 John W. Jordan All rights reserved.

Copy under terms of the GNU Free Documentation License


INTRODUCTION


Dante is a program that produces a recursive descent parser from a language definition. It is similar to other compiler tools such as the standard Unix tools YACC or BISON. However, YACC and BISON use a more powerful technique and can compile languages that recursive descent cannot. Dante is intended for small languages and especially for command languages and data description languages. Dante uses the "C" programming language and produces "C" code.


Dante was inspired by the book "Compiler Construction" by Niklaus Wirth. Dante follows his Extended Backus Naur Form (EBNF) but with the notation changed to more closely resemble BISON and YACC.


For our purposes, a compiler has three software modules. The first is the lexical analyzer or lexer. This separates the input text of the language being compiled into individual symbols that are often called terminal symbols or tokens. These correspond to the words of the language. In addition, the lexical analyzer will group the input symbols into classes and assign a class type to each symbol. Types allow us to refer to entire (sometimes infinite) groups of tokens by a single term. All members of a type share a common attribute that is of interest.


The lexer takes the input words that are represented by their symbol (value), and associates the appropriate type with them. In this way, each token has a type and a value.


The output of the lexical analyzer is a continuous token stream of the form:

[type value], [type value]...


As an example, for the English sentence - "John wrote Dante." a lexer might produce:


[noun John ] , [verb wrote], [noun Dante]

Tools for automatically generating lexical analyzers are LEX and FLEX. The documentation for these describes their use. Simple lexical analyzers can also be written by hand. Dante also provides support for building a lexical analyzer.


The second compiler module provides syntax analysis which identifies legal sentences of the language constructed from the symbols supplied by lexical analysis. It also has some sort of error reporting capability to aid the user. This is the module that is automatically produced by Dante. Another term for this module is parser. Because the lexical analysis module determines the type of each token, the parser stage only has to deal with types, which is a great simplification.


The third module deals with the semantics or meaning of the sentences once they are identified by syntax analysis. Usually, this module has action routines which are called upon to take the appropriate action for each correct sentence. These are embedded within the language definition used to define the syntax.


As Wirth points out in his book, the first two modules can be automated but the third resists automation because of the wide spectrum of actions required by different applications. One of the motivations for Dante is to provide additional support for the action module for certain applications.


DANTE DEFINITION LANGUAGE


Dante's definition language is based on Wirth's EBNF with some notation changed to be more like YACC or BISON. It has three parts - rules, actions, and directives.


A rule consists of a name followed by a colon (:), the rule body ( which we will call an expression ) and a terminating semicolon (;) :


name : expression ;


The body (expression) of a rule consists of terminal symbols (or tokens) of the target language and references to other rules. It is necessary for Dante to distinguish between the tokens and the rules. We will use uppercase for tokens and lower case for rules. This choice is simply to make Dante look more like YACC or BISON. The uppercase tokens are immediately converted to lower case internally.

An example of a rule is:


x: A INTEGER;


Rule x specifies an input of type A followed by an input of type integer. The rule:


y: A INTEGER z;


Specifies an input of type A followed by an integer followed by a reference to rule z. Control then goes to rule z to determine the rest of the input. Each rule returns true or false depending on whether the input agrees with the definition described by the rule.


A sequence of inputs is specified by successive tokens:


x: A B ;


This rule requires an input of type A followed by an input of type B. If the input is not of type A then the rule fails and returns false. If an input of type A appears then it must be followed by a type B, otherwise an error occurs.


Alternate inputs can be specified with the or ( | ) operator:


x: A | B ;


This rule matches an input of either type A or type B.


Dante also provides an iteration operator:

x: A < B > ;


This rule matches an A followed by zero or any number of B's. To define a positive integer as one or more digits:


integer : DIGIT < DIGIT > ;


Here we assume that tokens of type DIGIT are supplied by the lexer - they appear automatically whenever the type DIGIT is specified.


Wirth's EBNF uses {} for its iteration operator. However, this notation is used in C and Java to enclose a block of code so Dante substitutes <> for iteration.


Dante also offers an optional operator:


x: A [ B ];


this rule matches an A followed by an optional B.


Finally, there is a not (~) operator. It reverses the success or failure of a token. For example:


x: ~A ;


will fail if the input is of type A, otherwise it will succeeded. The not operator is useful for writing lexical functions. Examples appear in the section on lexers.. The not operator isn't necessary for parsing. (Nor is it necessary for lexers either, but it provides a connivence).


Directives are used to add an attribute to a token, or to select Dante output . All directives must appear after the rules section as they often modify the internal structures built by the rules. Directives will be further discussed in a subsequent section.


Precedence of Operators for Dante


Languages usually have precedence rules for their operators. In Dante a sequence has precedence over a choice. For example:


x : A B | C D ; rule 1


does not mean an A followed by a choice of B or C followed by a D - that is - rule 1 is not equal to:


x : A ( B | C ) D;


Because the sequence has precedence over the choice, rule 1 is interpreted by Dante as:


x: ( A B ) | ( C D ) ;


Therefore the choice is either an A B sequence or a C D sequence.


However, suppose we wanted a rule specifying a type A followed by a choice of B or C followed by a D. Then parenthesis may be used to alter the default precedence and the rule would be:


x: A ( B | C ) D ;


In all but the simplest rules it is perhaps good practice to use parenthesis rather than rely on the default.


DANTE ACTIONS


So far the definition of Dante is sufficient to build recognizers - programs that recognize legal input strings. Sometimes a recognizer with good error reporting is very useful to test programs that are being written. However, it is almost always necessary for the compiler to do something useful when it parses the target language. This requires the third module of the compiler - semantic analysis or action module. Dante has three methods for attaching actions.


Method 1


The first method is similar to YACC or BISON, although there are some differences in its use, because of the different parsing techniques used. Actions are C code added between open and close braces - "{" ..... "}". The containing {} are discarded. If additional {} appear nested inside, they are retained. An example of a rule with actions is:


tst: A { acode } B { bcode }

| C { ccode } D { dcode } ;


The code will be executed if the associated node is true - that is, if the current input token is of the correct type. Code can also be added to the rule itself:


tst: { local_code } A { acode } B { bcode }

| C { ccode } D { dcode } ;


Local code has a scope local to the function generated for the rule.


Code with file scope that is available to all functions can also be added before the first rule:


{ static_code }

tst: { local_code } A { acode } B { bcode }

| C { ccode } D { dcode } ;


Dante will produce this code:


static_code # Static code is placed here.

int

par_tst ( PAR *par)

{

local_code # Local code is placed here.


if (cmp(par, TYPE_a)){acode} else {goto l1;}


if (cmp(par, TYPE_b)){bcode return 1;}

else{par_error(par, "tst", "b");}


l1: if (cmp(par, TYPE_c)){ccode} else {return 0;}


if (cmp(par, TYPE_d)){dcode return 1;}

else{par_error_t(par, "tst", "d");}

}


It is also legal to have a rule (called an action rule) whose body consists only of a action:


act_x: { code };


Method 2


The use of braces is a flexible method to add code and action routines, and it can be used exclusively. However, there is an additional method which can be used when the action is a function call:


{ static_code }

tst: { local_code } A @act_a B @act_b

| C @ act_c D @act_d ;


act_a: { acode } ;

act_b: { bcode } ;


The symbol @ specifies an action routine that is a function call. In the above example, actions for act_a and act_b are defined as action rules, act_c and act_d are assumed to be supplied by procedures external to the Dante definition.


What about calling an action rule just like any other rule:


tst: A act_a ;


act_a: { acode };


Although legal, this method is not recommended. The rule act_a will generate mechanism to test its validity and will result in an error message unless it is made to always return true. It will also produce an additional internal node - Dante avoids this for other action routines. The additional overhead is avoided by using the unitary operator @.


Method 3


The third method is to replace the braces by a code reference. Sometimes the addition of code using the {... } notation degrades the readability of the target language rules. In this case the { .. } notation can be replaced by a reference of the form & name, where name is an alphanumeric identifier that identifies each code statement. The code reference is used within a rule as a place marker. There must be an action rule to define the code to be substituted in place of the marker. No new functionality is provided by using a code reference; its purpose is to allow the simplification of the parser rules. In effect, it provides a simple macro capability.


tst: A &act_a B &act_b

| C &act_c

;

act_a: { code }

act_b: { code }

act_c: { code }


The operator @ can be thought of as producing a function call, while the operator & produces inline code.


There is a difference between the use of actions in YACC and BISON and in Dante. In YACC or BISON, actions are added to the end of a rule. This restriction is to allow backup during parsing, so actions cannot be applied until the correct parse of the rule is determined. This is not absolute, it is sometimes permissible to add an action within a rule - BISON or YACC will in effect add another rule to accomplish this result. For Dante, it is permissible (and often necessary) to add an action after any rule component, as in the examples above.


Multiple actions of all three types may be attached to a node. They will be executed in the order of bstings, code references, and function references.


RESTRICTIONS


There are a number of restrictions that are inherent with the recursive descent parsing method, and others that are specific to Dante.


Null Rules


A null rule such as x: ; is not legal. A rule containing only an action such as x: { code }; is legal.


Null Choices


A Null choice such as x: A | { action } ; is not legal. A choice must be a terminal symbol or rule, it cannot be an action. Actions must be attached to tokens, not operators.



Distinct Choices for Alternatives


Each choice must begin with a distinct symbol. For example:


x : A

| A B ;


x : A B

| A ;


are illegal, because both choices begin with the token A and the second choice will never be chosen. A legal way to write this rule is: x : A [ B ]; or an A followed by an optional B.


The rule:


x: A B

| A C ;


should be written as x: A ( B | C ) ;


Repeat operator


Because both the repeat <> and choice operators [] succeed for zero occurrences, they will always return true. Therefore:


x: < A> # Zero or more A's

| B

;

is not legal because the first choice will always succeeded, and the second will not be tried. This is legal:


x: A < A > # One or more A's

| B

;


A rule like:


x: <A> <B> <C>;


that involves a sequence rather than a choice is legal and is used in the full Dante definition.


Optional Operator


Similar restrictions apply to the optional operator. When used as a member of a choice, it is important to remember that it will always succeeded. Therefore


x: [A]

| B;


will not perform its choice function as the first choice will always succeeded.


There is an additional restriction for the optional operator. It cannot be used to begin a rule. For example:


x: [A] B;


is not correct. This restriction is not fundamental, but accepting it simplifies Dante. The restriction may be removed in future releases. Suppose we wished to define a signed integer. It is tempting to use:


integer: ['-'] D < D >; but Dante does not allow a rule to begin with the [] operator. A valid signed integer is:


integer: '-' posint

| posint;


posint: D < D >;

In general


x: [A] B ;


can be written as:


x: A B

| B ;


Left Recursion


Both YACC and BISON use left recursion for iteration. For example an integer can be defined as:


integer: integer DIGIT

| DIGIT;


This rule states that an integer is either a digit or an integer followed by a digit. Left recursion is not allowed for recursive descent parsing, as it will result in an infinite loop.


Right Recursion


Recursive Descent parsing allows right recursion. Use of right recursion is not recommended for Dante because it has an iteration operator. However, right recursion is not illegal, and is occasionally useful. An appendix offers some comments on right recursion.


SPECIAL TOKENS


Up to now we have denoted rules with lowercase symbols and tokens with upper case symbols. This is consistent with BISON and YACC conventions. However, there is utility in further dividing tokens into additional classes.


Reserved Words


Reserved words have a specific, defined meaning in a language such as "if" or "while" or "for" in "C". There is a one to one correspondence between the type of each reserved word and its value. Reserved words are in effect string literals, or single valued tokens.


Usually the lexer recognizes the reserved words. Initially, they are classed as identifiers - alphanumeric types. Then a reserved word table is searched to re-classify the identifier as reserved. This procedure makes the identifiers and reserved words disjoint - neither can be used in place of the other. Dante automatically builds a reserved word table, and it needs to know which tokens are reserved and which are not. Dante provides two methods to define reserved words. The first ( and greatly to be preferred ) is to enclose reserved words in double quotes, - "if", "while". The quoted reserved words can be upper case or lower case or any combination, exactly as they should appear in the language to be compiled.


NOTE: It is important to note that quotes are used to define a reserved word to Dante. The reserved words thus defined will later appear as input in the compiled language without quotes. So the lexer for that language must be able to detect these reserved words and separate them from identifiers when they don't have quotes.


The second method is to specify the reserved word as an upper case type and then use the dan_set_res directive to mark it as reserved. For Dante, the quoted method is to be preferred.


Literal


Dante allows literals - character values inside single quotes. These are used to specify operators '+' , '>', '/' etc. Dante will also allow multiple character operators such as '==', '>=', etc. Currently, multiple character operators are restricted to two characters. See the section on lexers for more information. NOTE: a literal is not the same as in the "C" language. It simply encloses a string of characters. There are no special characters such as a backslash. For example '\' is the character \. For lexical functions literals can be used to define character values.


CORE DANTE DEFINITION


Since the syntax of EBNF is written in EBNF, likewise, a definition of Dante can also be written in the Dante dialect of EBNF. Dante was written starting with this definition and expanding it as necessary. As a result Dante will compile itself.


# Dante definition written in Dante (Modified EBNF ).

dan: < rule >;

rule: IDENTIFIER ':' expr ';' ;

expr: term < '|' term > ; # Gives a choice lowest precedence

term: factor < factor > ; # Gives a sequence medium precedence

factor: IDENTIFIER # Gives repeat and optional operators highest precedence.

| QSTRING # reserved words

| LITERAL # operators

| '<' expr '>'

| '(' expr ')'

| '[' expr ']'

;


This is the core or basic Dante definition. It will be expanded to incorporate actions and directives.


PARSER OUTPUT


A parser usually produces some sort of intermediate structure, often a parse tree. Following Wirth's book, Dante produces a syntax graph (SG) as its parser output. A SG consists of nodes corresponding to each terminal symbol or rule in the language definition. The nodes are connected by two arcs, one that shows the path to be taken if the node's symbol matches the input from the lexer and the other is the path for failure to match. We will call these (following Wirth) respectively the successor arc (SUC) and the alternative arc (ALT). They could be just as well labeled true and false, 1 and 0, or success and failure.


The rule

tst: A B

| C d

;

generates this SG:


NAME

SUC

ALT

A

B

C

B

RTN 1

ERR 1

C

D

RTN 0

d

RTN 1

ERR 2


Or in syntax graph form :


[ tst ] -----[ A ] ---------[ B ]------1 Success

| |

| |

| 2 Error 1

|

|

[ C ] ---------( d ) ------1 Success

| |

| |

0 Failure 2 Error 2


where [] means compare to input, () call a rule, and 0,1,2 means return failure, success, or an error. Horizontal lines lead to the successor node and vertical line to an alternative node.


A node can have an associated action routines that are executed when the comparison operation at the node results in success (true). Then the successor arc is taken. There is no action routine for the failure path. Each true arc can be labeled with the associated action.


Dante generates "C" code from each SG node using the following pattern:


label: if (operation) { actions; goto label_x; } else { goto label_y; }


Each rule becomes a separate C function, other nodes generate IF or CALL statements. For our example ( which has no actions), Dante generates:


int

par_tst (PAR * par)

{

if (cmp (par, TYPE_a)) {} else {goto l1;}


if (cmp (par, TYPE_b)) {return 1;} else {par_error (par, "tst", "b");}


l1: if (cmp (par, TYPE_c)) {} else {return 0;}


if ( d (par)) {return 1;} else {par_error (par, "tst", "d");}

}


Par is a structure used throughout the parser.

For each node corresponding to a terminal symbol an if statement is produced. The conditional part of the if is the function cmp which compares the required terminal to the input. The cmp function calls the lexer as necessary for the next input symbol.


int cmp (PAR *par, int req_type)

{

/* If there has been a match a new input symbol is required. */

if (par->match)

par_tst_lex (par); # Calls lexer for next input symbol.

if (req_type == (par->type)) { par->match = 1;}

else {par->match = 0;}

return par->match;

}


THE PAR STRUCTURE


Dante automatically produces a structure called PAR. It is defined in the file par.h. This structure is passed to each Dante routine and it provides a method of passing information that preserves the reentrant nature of the parser. PAR contains a number of variables that can be referenced by action routines. The most important is:


par -> symbol


This string is the current symbol read by lexical analysis. Symbol is a pointer to a character array.

It is important to note that these values will be transient - for example symbol is changed each time lexical analysis reads a new symbol. This is why Dante programs may have an action after each token, even if its purpose is to just capture the current symbol for later use.


par->type


contains the type of the input determined by the lexer. Internally, types are represented by integers. The terminal of type A will be represented internally by TYPE_a. Single character literals are represented by the character value itself. Multiple character literal have an assigned integer value.


par->match


is set to true (1) or false (0) depending upon the input matching the parser requested type.


PAR also contains additional variables:


par -> i_value of type int.

par -> d_value of type double

par -> s_value of type char *

par -> l_value of type long


The user can use these variables in and between action routines.


The number of PAR variables may be too limited for some action routines. PAR also contains a pointer for attaching a structure for use by the action routines:


void * action;


The action structure will then passed to all Dante procedures via the PAR structure. In most cases, it is simpler to just add to the par structure. In doing so it is important to leave the Dante generated part untouched, because library functions are compiled with the basic structure.


MULTIPLE INPUT FILES


Sometimes the input to be parsed is in more that one file. It could well be in a sequence of files. The input can be switched by adding a rule that calls the action par_file. In the following example the rule file accomplishes this switch of input files. This is done recursively, and when the new file is done, the input switches back to the original file and resumes reading where it left off. If the new input file also has a file statement then the recursion will extend down one more level, and so on. Qstring is a quoted string.


file: FILE QSTRING{ par_file (par, par->symbol); } ;


A possible parser input file might be:


file "foo1"

file "foo2"

file "foo3"


This would parse the statements in the three files in succession. The use of the word FILE has no significance as it is just another rule name. Another word such as INCLUDE could be used as well. It is the associated action that switches the input streams.


EXAMPLE CONFIGURATION FILES


One use of Dante is to provide a simple language parser for system configuration files. The configuration file is written in the target language, and when parsed it updates objects in memory, or performs some other type of configuration. We will assume a target language for configuration files that is of the form keyword - value.


Consider a configuration file that contains a number of task definitions. A Dante definition for parsing task statements might be defined as:


cnf: <task>;

task: "task" "id" INTEGER "priority" INTEGER "path" STRING;


The body of this rule consists only of tokens which will be provided by the lexer.


The first rule is "cnf", the generated code will be in the file "par_cnf.c ". This is a Dante convention for linking. The first rule will name the files that Dante produces.


Note that in the example, a task statement in the target language must be written exactly as indicated - for example:


task id 1 priority 23 path "/usr/bin/sh" is OK


If the statement is written with the order of parameters changed:


task id 1 path "/usr/bin/sh" priority 23


an error results, even though the parameters are in the form of a key word followed by a value they are also positional because of the language definition. A definition which allows any order of the parameters is:


start: <task>

task: "task" <parms> ;

parms: "id" INTEGER

| "priority" INTEGER

| "path" STRING

;


Or, somewhat simplified:


start: <task>

task: "task"

<

"id" INTEGER

| "priority" INTEGER

| "path" STRING

>

;


ACTION ROUTINES FOR TASK STATEMENTS


The task statement can serve as an example of how action routines are added:


cnf: < task >;

task: { #include "task.h"

TASK task; }

"task"

"id" INTEGER { task.id = atoi (par -> symbol); }

"priority" INTEGER { task.priority = atoi(par->symbol); }

"state" INTEGER { task.state = atoi(par->symbol); }

"name" STRING { strcpy (task.name, par -> symbol); }

"path" STRING { strcpy (task.path, par -> symbol); }

"end" { save_task ( &task); }

;


Immediately following the task: is some code that will appear at the beginning of the procedure generated for the task rule, i.e. It will have function scope. The file task.h is assumed to be defined and available when the parser is compiled. Also defined is a task structure, allocated as an automatic variable. Once the parser has recognized ID followed by an integer the variable par -> symbol will contain the character string value of the integer. This can be converted by the atoi function and assigned to the task structure member. A sample input file might be:


task id 1 priority 20 state 1 name "task1" path "/bin/task1" end

task id 2 priority 20 state 1 name "task2" path "/bin/task2" end

task id 3 priority 20 state 1 name "task3" path "/bin/task3" end


Within each task statement the state has an associated integer value. A better choice would be an enumeration of possible states. A specification to accomplish this might be:


{ #define SYM strdup(par -> symbol)

#define INT atoi(par -> symbol)

#define IVALUE (par -> i_value)

}

cnf: < topics >;

topics: file | task ;


task: { #include "task.h"

TASK task;

}

"task"

"id" INTEGER { task.id = INT; }

"priority" INTEGER { task.priority = INT; }

"state" tstatus { task.state = IVALUE; }

"name" STRING { strcpy (task.name, SYM); }

"path" STRING { strcpy (task.path, SYM); }

"end"

;

tstatus: "not_ready" { IVALUE = 1; }

| "ready" { IVALUE = 2; }

| "running" { IVALUE = 3; }

| "waiting" { IVALUE = 4; }

| "done" { IVALUE = 5; }

;


include_file: INCLUDE_FILE QSTRING { par_file (par, SYM); } ;


There are a number of new ideas here. First, some code has been placed at the top. This code will appear before any of the procedures - it will have file scope. It has been used to define three macros - SYM , INT, and IVALUE - which are used in the action routines. Their only purpose is to make the rule more readable. Within the rule tstates the variable par -> i_value is set, it is then referenced within the task rule to set the state variable in the task structure.


The task input file might now be:


task id 1 priority 20 state not_ready name "task1" path "/bin/task1" end

task id 2 priority 20 state not_ready name "task2" path "/bin/task2" end

task id 3 priority 20 state not_ready name "task3" path "/bin/task3" end


The enumeration has been specified such that task statements using integers will also work. Direct numerical values are still used within the tstatus rule. An improvement might be to use a "C" language enumeration statement, along with the convention that enumeration values are in upper case.

{

#include "tstatus.h"

#define SYM strdup(par -> symbol)

#define INT atoi (par -> i_value)

}

cnf: < topics >;

topics: file | task ;

task: { #include "task.h"

TASK task;

}

"task"

"id" INTEGER { task.id = IVALUE; }

"priority" INTEGER { task.priority = IVALUE; }

"state" tstatus { task.state = IVALUE; }

"name" STRING { strcpy (task.name, SYM); }

"path" STRING { strcpy (task.path, SYM); }

"end"

;


# These reserved word are upper case.

tstatus: "TASK_NOT_READY" { IVALUE = TASK_NOT_READY; }

| "TASK_READY" { IVALUE = TASK_READY; }

| "TASK_RUNNING" { IVALUE = TASK_RUNNING; }

| "TASK_WAITING" { IVALUE = TASK_WAITING; }

| "TASK_DONE" { IVALUE = TASK_DONE; }

;


In this example the include file tstatus.h has been included to define the enumeration. Often, "C" enumeration values are written in upper case. If the enumeration values in the target language are to be in upper case, this can be specified by a quoted upper case reserved word.


Now assume that we wish to add a period measured in microseconds to the task definition.


PERIOD INTEGER time_units;


time_units: MICROSECOND

| MICROSECONDS

| MICROSEC

| MICRO

| MILLISECOND {IVALUE *= 1000;}

| MILLISECONDS {IVALUE *= 1000;}

| MILLISEC {IVALUE *= 1000;}

| MILLI {IVALUE *= 1000;}

;

These definitions will force the user to specify units and will convert the actual input to a consistent internal representation of microseconds.


Finally, note that other methods of adding actions can also be used:


task: &a

"task"

"id" INTEGER &b

"priority" INTEGER &c

"state" tstatus &d

"name" STRING &e

"path" STRING &f

"end"

;


a: { #include "task.h" TASK task; } ;

b: { task.id = INT; } ;

c: { task.priority = INT; };

d: { task.state = IVALUE; };

e: {strcpy (task.name, SYM); };

f: {strcpy (task.path, SYM); };


The simplification will be more pronounced for more complex rules than the task example.


Some configuration files use a separator between the keyword and its value. These separators can be added as strictly syntax elements (noise words) without associated actions:


"priority" ':' INTEGER


"priority" '=' INTEGER


"PRIORITY" INTEGER # Priority must be in upper case in configuration file.


EXAMPLE FOR A BOOLEAN ALGEBRA


For this example, consider logical or Boolean statements. The terminal symbols consists of logical variables having the value true or false and the operators

not ~

and &

or |

In addition there are precedence rules that apply to the operators:


  1. not has the highest precedence.

  1. and has the second highest precedence, and,

  2. or has the lowest precedence.


A typical logical expression might be: x = a | b & c | d;

Because and ( & ) operations have precedence over or ( | ) operators this statement is equivalent to:


x = a | ( b & c ) | d;


and the and operation will be done before the or operation. By using parenthesis the user can specify the exact meaning of a statement and override the default precedence:


x = (a | b) & ( c | d);


specifies that the or operations are first, then the and operation.


The first step is to define a recognizer that will parse correct logical statements.

# Parse logical statements in infix form. (This line is a comment.)

start: < statement > ;

statement: IDENTIFER '=' expression ';' ;

expression: term < '|' term > ;

term: factor < '&' factor > ;

factor: IDENTIFER

| '~' factor

| '(' expression ' )' ;

This definition gives precedence to and ( & ) over or ( | ). It first gathers up the identifiers connected by & to form a term. Only then does it connect the terms into an expression using the | operator. The not operator ~ is applied at the factor level giving it the highest precedence of all. Let's add actions that will convert the input statements written in infix to postfix form.


In postfix (often called Reverse Polish) two operands connected by an infix operator are reordered so that the operator follows the two operands. For a urinary operator such as ~ the single operator follows the operand. No parenthesis is required for the postfix form, which greatly simplifies many operations. For example:


infix form a & b becomes postfix form a b &

infix form ~ a becomes a~


The statement:

x = a & b | c & d;


will be parsed ( by connecting the & operands first to conform to the precedence requirements ) as if it were written as:


x = (a & b) | (c & d);


and will result in the postfix statement:


x a b & c d & | =


The infix statement:


x = a | b & c | d;


will be parsed as:


x = a | ( b & c ) | d;


and in postfix:


x a b c & | d | =

By using parenthesis the user can specify the exact meaning of a statement in infix form and override the default precedence.


A parser which prints the postfix form is:


# Parse logical statements in infix form and output Polish statements.


start: < statement > ;


statement:

IDENTIFER { act_out (par -> symbol); }

'='

expression { act_out ("="); act_out ("\n"); }

';'

;

expression: term < '|' term { act_out ("|"); } > ;

term: factor < '&' factor { act_out ("&"): } > ;

factor: IDENTIFER { act_out (par -> symbol); }

| '(' expression ' )' ;


The single action routine act_out simply prints what it is passed. In this case the action routine is not really necessary, and could be replaced with a print statement. It is worthwhile to take a closer look at why this simple example works. Take the simple input to the generated parser "a & b". Initially, we descend to the term rule. It calls the factor that will recognizes the operand "a" and it is immediately output. Returning to the term rule it recognizes the "&" operator but it isn't output because operators must be delayed until after the operands. But the occurrence of this operator must be "remembered" or recorded. Back down to the factor rule which recognizes the operator "b" and outputs it. At this point, the end of the term rule has been reached, and the "&" operator is output. It is known that the "&"operator has occurred because its the only operator in the term rule. Recording its occurrence was entirely implicit.

Now consider an analogous but slightly more complex example - the multiplication and division operators of arithmetic. Typical inputs might be "a * b" or "a / b". YACC would allow a term rule like this:


term: factor '*' factor

| factor '/' factor


but this isn't legal for recursive descent parsers because each choice must be initially unique. A legal alternative is:


term: factor < mul_div factor> ;

mul_div: '*' { save_oper (par);

| '/' { save_oper (par); }

;

but now the occurrence of the operator must be explicitly saved (in a stack) so that the proper one can be output at the end of the term rule.


The example directory has an example (examples/log) where the operators are stored in a temporary stack. That example also builds a tree as its output.


LEXICAL ANALYSIS


The parser generated by Dante requires a lexer. This may be provided by using LEX or FLEX or written by hand in "C", or in Dante.


Dante provides help for building a lexer. As might be expected this requires some additional information from the user.


Using Flex


A simple method for creating a lexer module is to use FLEX or LEX. Dante will generate a prototype FLEX lexer, but the user must provide regular expressions for non reserved tokens.

The directive dan_flex_def is used to define non-reserved types and provide FLEX with a regular expression for those types. For example:


dan_flex_def IDENTIFIER "[a-zA-Z][a-zA-Z0-9_]+ " ;

dan_flex_def QSTRING "\\\"[^\"n]*\\\"" ;

dan_flex_def INTEGER "-?[0-9]+" ;

dan_flex_def DOUBLE "-?[0-9]+.[0-9]+" ;


Each regular expression is in the form specified for FLEX, only put into a quoted string.


When the dan_flex_def directive is used a FLEX lexer is generated in the file flex_xxx.flex. For the FLEX lexer to be used, the suffix .flex must be changed to .l as required by the flex program. This naming convention is used to avoid overwriting a FLEX lexer which has been modified.


I'm not certain that this much FLEX interface is warranted or useful, so its more or less experimental.


Using Lexer Functions


A different method of generating a lexer is to use functions for non-reserved tokens. In effect, the functions provide a rule to determine the type of each input symbol. These functions are then callable as rules. These functions may be called lexical functions. For example the default lexer generated for Dante is:


dan_lex: lex_space

(

lex_identifier

{ par->type = par_dan_rwtbl (par, TYPE_identifier); }

| lex_bstring { par->type = TYPE_bstring; }

| lex_integer { par->type = TYPE_integer; }

| lex_literal { par->type = TYPE_literal; }

| lex_qstring { par->type = TYPE_qstring; }

| lex_operator

)

;


Here, the lex_xxx are library lexical functions. A sample set is included in danlib. The first lex_space, eliminates white space and comments. Since it functions as a rule it must return 1 because we always want the other alternatives to be tried. The other functions must return 0 or 1 depending upon their matching the input stream. In the above example, identifiers and reserved words are both alphanumeric types. A reserved word list is searched to distinguish between them. This means that a reserved word cannot be used as an identifier. Conversely, an alphanumeric type that is not on the reserved word list becomes an identifier. The function par_xxx_rwtbl is generated by Dante, and is used to scan the reserved word list. A default value is passed to the function to be returned as the value of the function if there is no match. Usually, the default value is the identifier type.


For an unusual language with no identifiers, zero is passed for the default. An error message results if a reserved word is not found.


All Dante rules have par_ appended to their names when code is generated, so the library functions will have names such as par_lex_xxx.


USING DANTE FOR LEXERS


The lexical functions can be written in DANTE, although it lacks some of the options of regular expressions. My experience, although limited, is that lexers may be more difficult to write than parsers, especially for simple languages describing configuration files. Library functions can alleviate this difficulty.


There must be some differences when Dante is producing lexer code instead of parser code. For example, it cannot use par->type or par->symbol because it is storing values in these to return to the parser. Instead, the structure par.h contains three integers to support lexer functions. They correspond to the variables used by the parser but are integers because the lexer input is characters. Dante operates in two different modes, one produces parser code, the other produces lexer code. For lexers it is important to include the directive dan_lex_fun in order to switch to the lexer mode.


Variable

Use

Corresponds to

par->lex_m

a flag which is set when the input character is matched

par->match

par->lex_c

The current input character

par->symbol

par->lex_t

The character type

par->type


There are two additions to Dante that facilitate the writing of lexers. Although they are in no way required, they considerably simplify lexer construction.


First of all, the input to a lexer is a stream of characters, and these can be described by character literals. But lexer code may be somewhat difficult to read if it contains a profusion of character literals. Some people prefer to use pneumonic names for these literals. For this reason, Dante has a directive to define a reserved word and set its internal type code value. This directive dan_type_code allows a type code, expressed as an integer, to be assigned directly to a token. This directive , like all directives, must appear at the end of a Dante definition.


Dante lacks an operator found in regular expressions - "any character but x ". To help in this situation a not operator (~) has been added to Dante. Its use is restricted to a specific situation. The use of the not operator is best illustrated by some examples. Its restrictions will be covered in a subsequent section.


A good starting point using Dante is a rule for recognizing an identifier that must begin with a letter and continue with a letter, a digit or an underscore.


identifier: letter < letter | digit | '_' >;

letter: 'A' | 'B' | 'C' ...

digit: '0' | '1' | '2' ...


These rules are perfectly legal but quite inefficient because Dante does not (currently) optimize its code for rules of this type. Although efficiency is not a primary goal of Dante, lexers are somewhat an exception because of the large number of characters processed. A simpler lexer results if a character has its type determined when it is first read. Instead of considering each character as having its own type and being a single valued type to the lexer, characters may be classified into disjoint sets and assigned a group type. All alphabetic characters can be grouped as a LETTER. Likewise digits are put in a group with type DIGET, etc. In this way, a rule for a letter is replaced by a type Of course, there must be a mechanism somewhere to identify the LETTER type. Just as the parser types are identified by the lexer, in the lexer these types are identified by the input module. In effect the input procedure is the lexer's lexer and it can absorb some of the work in classifying the input.


#par_lex_identifier

identifier: LETTER @lex_accept

< LETTER @lex_accept

| DIGIT @lex_accept

| UNDERSCORE @lex_accept

> ;

dan_lex_fun; # This important directive tells Dante to produce lexer code.

dan_type_code LETTER 76 # ascii value for L

DIGIT 68 # ascii value for D

UNDERSCORE 95; #ascii value for underscore


Accept is a library routine that accepts the input character and adds it to par->symbol.


This lexical function could also be written as:


#par_lex_identifier

identifier: 'L' @lex_accept

< 'L' @lex_accept

| 'D' @lex_accept

| '_' @lex_accept

> ;


It is probably a mater of opinion of which form is better.


An additional example is a rule for recognizing a quoted string which begins with a quote and ends with a following quote. The delimiting quotes are discarded. Quote characters are kept if proceeded by a black-slash (\).


# par_lex_qstring

lex_qstring: QUOTE # FIRST character is a quote.

<

~ QUOTE # Ends iteration at second quote.

( NLINE @error # Checks for a non-terminated string.

| BKSLASH ANY @lex_accept # Allows quotes in a quoted string.

| EOF @error # Checks for an non-terminated string.

| ANY @lex_accept # Accepts any other character.

)

> ;

dan_lex_fun; # This important directive tells Dante to produce lexical function code.

dan_type_code QUOTE 34; # ascii value for a quote

dan_type_code NLINE 10; # ascii value for a new line

dan_type_code BKSLASH 92; # ascii value for a backslash

dan_type_code EOF 0; # Dante uses 0 for end-of-file

dan_type_code ANY 1; # Matches any character


The first character test is for a quote input character, and if found, the rule accepts subsequent valid characters. The rule returns successfully when a second quote is encountered. The not (~) operator specifies failure when a quote is encountered, instead of success. This ends the iteration.


Dante uses 0 for end-of-file following Flex's choice. New line or end-of-file characters are error conditions indicating an non-terminated string. The type ANY has a special value (1) that the lexical comparison function always matches. Finally, accept is an action routine to assemble the string into the par->symbol array.


There are instances where Dante is not as flexible as FLEX for building lexers because it has no provision to backup during parsing. Again, somewhat detailed knowledge of how Dante works allows workable solutions. Dante does not try to match the longest rule. Assume that a language has both integers and floating point numbers. A floating point number might be defined as two integers joined by a decimal point.:


integer: an integer definition?

double: INTEGER'.' INTEGER;


Dante would have a problem with this because it would start matching the integer rule but if it finds a decimal point it is unable to backup and try the double rule.


One method is to define a lexical function number which includes both types:


lex_number: integer &int_type [ '.' posint &dbl_type ];

integer: '-' posint #FIRST char is '-' or digit

| posint;

posint: DIGIT @lex_accept < DIGIT @lex_accept >;

int_type: { par->type = 'I'; };

dbl_type: { par->type = 'D'; };


This function returns a type of 'I' for an integer or 'D' for a double (float). Assuming the language definition has types INTEGER and DOUBLE the lexical function number would be called from within the lexer by a rule of the form:


token:

lex_number

{if (par->type == 'I')

par->type = TYPE_integer

else par->type = TYPE_double}


Note that this definition restricts the form of a double to necessitate a decimal point, but this is sometimes an advantage for configuration files. Although backup is not used the lexical function is allowed "to change its mind".


Grouping the input characters into classes in the input function has its disadvantages as well as advantages. As an example consider a library function for a double which allows scientific notation:


# Lex_double

lex_double: integer [ '.' @lex_accept posint [ exponent ]] ;

exponent: LETTER test @lex_accept sign posint ;

test:

{

if ((par->lex_c == 'e') || (par->lex_c == 'E')) return 1;

else error;

};

sign: '+' @lex_accept

| '-' @lex_accept ;

integer: '-' @lex_accept posint

| posint;

posint: DIGIT @lex_accept < DIGIT @lex_accept > ;

dan_lex_fun ;

dan_type_code DIGIT 68 LETTER 76;


Where we would like to check for an 'e' or 'E' in the exponent we are forced to first check for a letter using LETTER (or 'L'), then add a test for the individual characters. This is because in par_lex_input function has assigned the LETTER ('L') type to letter.


Additional examples are contained in the lib directory. An example directory examples/tst_lex illustrates one method of testing a lexer.


Operators


Operators are defined as literals using single quotes. They may be single or multiple characters long. Dante itself only uses single character operators, but allows multiple character operators (currently two characters long) to be defined. Because the operators will be different for each language to be compiled Dante will generate a specific par_lex_operator.dan when it generates a default lexer.



However, the library does contain a default par_lex_operator.dan which can be used for single character operators. It is shown here because it is somewhat different in that it uses a C library function ispunct . It also includes a test for end of file.


# lex_operator

lex_operator: EOF {par->type = 0;}

| punct {par_lex_accept(par); par->type = par->lex_t;}

;

punct:

{

if(par->lex_m)

par_lex_input(par);

par->lex_m = (ispunct(par->lex_c))? 1:0;

return par->lex_m;

};

dan_lex_fun ;

dan_type_code EOF 0 ;


Note that the punct function mimics the CMP function that Dante generates automatically to compare token values that are represented by an integer code.

Lexer Input


When Dante is used to build a lexer, the resulting procedure mimics the structure of a parser. A parser calls upon the lexer for its input tokens. A lexer will likewise call upon an input procedure for its tokens - all of which are characters. The input procedure returns each character value and its type. The input procedure is a "C" function (par_lex_input.c )of the form:


int par_lex_input (PAR *par)

{

par->lex_c = par_get_char (par);

par->lex_t = par->lex_c;

if (isspace(par->lex_c))

{

par->lex_t = 'S;

if (par->lex_c == '\n') par->lex_t = '\n';

}

else if (isalpha(par->lex_c)) par->lex_t = 'L';

else if (isdigit(par->lex_c)) par->lex_t = 'D';

else if (par->lex_c == EOF)

{

par->lex_c = 0;

par->lex_t = 0;

}

return par_lex_t;

}


Typing corresponds to the "C" library functions isxxx with the exception that the new line is not considered a space character. This allows the new line to be used as a token in rules where it is significant.


Character Type Table

Character lex_c

Type lex_t

Isalpha

'L'

Isdigit

'D'

Isspace

'S'

new line '\n"

'\n' new line is not typed as a space.

Isprint

Lex_c type is char. value

not isprint

'E' error condition

end of file

0 zero is used as end of file


Any non-printable characters are typed as 'E' to indicate an error. They should never occur in a valid input file.


The input function is included in the pardan library. For some applications the input function may require modification.


Because the input function is called for each character, some further optimization can be done and may be advantageous. By generating a table (ctypes) of char types that corresponds to the functions in the above example the input routine can be simplified:



int par_lex_input (PAR *par)

{

par->lex_c = par_get_char (par);

if (par->lex_c == EOF)

par->lex_c = 0;

par->lex_t = ctypes[par->lex_c];

return par_lex_t;

}


First Symbol


For the Dante lexer we can make a table for the first symbol (character) of each lexical function.


Type

First Symbol

Identifier

Alpha

Reserved word

Alpha

Bstring

{

Qstring

"

Dstring

$

Literal

'


The table shows that except for an identifier and a reserved word, the lexer can decide the type of the input symbol from the first character. There is a conflict between an identifier and a reserved word. This is resolved by only including the identifier in the lexer. Reserved words are then separated from identifiers by searching the reserved word table in an action routine.


The first symbol for an integer and a floating point number is:


Type

First symbol

Integer

- or digit

Double

- or digit


The conflict between these types can be resolved by replacing them by a number type for both. The number type returns an indicator for integer or double and the final type is assigned by an action routine.


Dante Default Lexer

Despite the wide spectrum of requirements for lexers, when the command line option -l is used, Dante will attempt to build a default lexer that is output in the file par_xxx_lex.dan. It is difficult to produce a lexer for every situation, so the default may require some modification. The lexer may be compiled separately from the main definition using the dan_sub_of directive, or it may be added to the main definition.


Not Operator


The not operator (~) has a limited and specific use. It succeeds for not A and fails for A. Assume that ANY is a type that matches any character in a lexical function. Then:


x: ~A ANY ;


will match any character except one of type A. A rule like:


x: < ~ A ANY > ;


will match an arbitrary length string of characters until it finds an A. In this case ~A is used to end the itteration.


SUPPORTING ROUTINES


Dante generates a number of output files. The first rule name in a Dante definition is used to name these files. We will use the string xxx to represent this name. It also generates some supporting routines that are necessary or useful for the complete parser. These routines will have to be modified or added to complete the parser. For this reason Dante will only generate these routines once. If there is an existing routine of the same name a replacement will not be generated. Dante modifies this procedure for some supporting routines. These are generated with a suffix that must be changed before use.


FILE

CONTENTS

PRODUCED

par_xxx.c

parsing routine

Always

par_xxx_rwtbl.c

reserved word table

not for a lexer

par_xxx_main.c

main

if none exists

par_xxx_file.c

Recursive call to input

Always

par.h

parser structure

if none exists

par_xxx_act.c

stub for actions

if none exists

par_xxx.flex

flex lexer

if flex lexer is selected

par_xxx_lex.dan

default lexer

if default lexer is selected

par_lex_operator.dan

Lexical function

If default lexer is selected

xxx.mk

Stub for makefile

Always


DIRECTIVES



dan_buffer_input

This directive specifies that input is from a buffer rather than a file. An example is in examples/cnf_buf.


dan_set_res IDENTIFIER

This is used to make a terminal symbol a reserved word. The preferred alternative is to put the reserved word in quotes.


dan_lex_fun

This causes Dante to produce code suitable for a lexical function rather than a parser. This directive is essential for lexer functions. Each lexical function should be compiled separately from the main definition for this reason. Lexer functions are located in the pardan library. The lexer code which calls these functions does not use this directive.


dan_type_code IDENTIFIER INTEGER ...

Each terminal symbol is assigned an internal type code which is simply an integer value. This directive changes the default value to the specified value. It is used to assign character values to terminal symbols for lexer functions.


dan_sub_of IDENTIFIER

This directive is used to separately compile par of a Dante definition as a subroutine. The identifier is the name of the main program. This directive will inhibit the generation of supporting routines. This directive is intended to allow separate processing of a lexer. Separately compiled routines can only refer to reserved words or types defined within the main routine.


dan_use_flex

This directive generates a lexer interface for use with FLEX.


dan_flex_def

This is used to add a FLEX definition. It will cause Dante to produce a prototype Flex lexer.


COMMAND LINE OPTIONS


Comand Line Option

Meaning

-v

Verbose - print details

-l

Generate default lexer

-f

Generate flex lexer

-n

Generate node list for Syntax Graph

-a

Print input to standard out for debugging

-b

Print lexer output for debugging

REFERENCES


    1. Wirth, Niklaus; Compiler Construction, Addison-Wesley, 1996,

ISBN 0-201-40353-6

    1. Gries, David; Compiler Construction For Digital Computers,

John Wiley and Sons, 1971, ISBN 0-471-32776-X

    1. Gauthier, Richard L.; Ponto, Stephen, D.; Designing Systems Programs,

Prentice-Hall, 1970

    1. Grune, Dick; Bal, Henri E.; Jacobs, Ceriel; Langendoen, Koen,G.

Modern Compiler Design,

John Wiley and Sons, 2000, ISBN 0-471-97697-0



Appendix 1 Dante definition


# Dante Definition


dan: [code] < rule > < dir >;


rule: IDENTIFIER @a_rule ':' expr @a_end ';';


expr: term < '|' term @a_or >;


term: factor < factor @a_and >;


factor: IDENTIFIER @a_iden <action>

| LITERAL @a_lit <action>

| QSTRING @a_res # Reserved words.

| BSTRING @a_bstr #For action rules expr can be a bstring.

| '(' expr ')' # Precedence operator

| '<' expr @a_rpt '>' # Repeat operator

| '[' expr @a_opt '] # Conditional operator

| '&' IDENTIFIER @a_cref #For local code reference.

| '@' IDENTIFIER @a_fref #For local code reference.

| '~' IDENTIFIER @a_not <action>

;


# File scope code.

code: BSTRING @a_bstr

| '&' IDENTIFIER @a_cref

;


# Actions on identifiers or literals.

action: BSTRING @a_bstr

| '@' IDENTIFIER @a_fref

| '&' IDENTIFIER @a_cref

;


# Dante directives

dir:

(

"dan_buffer_input" @a_buf_input

| "dan_flex_def" IDENTIFIER @a_flex_name

DSTRING @a_flex_def

| "dan_lex_fun" @a_set_lexer

| "dan_no_support" @a_no_support

| "dan_reserved" < IDENTIFIER >

| "dan_sub_of" IDENTIFIER @a_sub_of

| "dan_type_code"

<

IDENTIFIER @a_tname

INTEGER @a_tvalue

>

| "dan_use_flex" @a_use_flex

) ';'

;

#Lexer - may be included here or compiled separately as a subroutine using #dan_sub_of directive.

dan_lex: lex_space

( lex_identifier #Look up reserved words

{ par->type = par_dan_rwtbl (par, TYPE_identifier); }

| lex_bstring { par->type = TYPE_bstring; }

| lex_integer { par->type = TYPE_integer; }

| lex_literal { par->type = TYPE_literal; }

| lex_qstring { par->type = TYPE_qstring; }

| lex_operator # Types defined within function

)

;


Appendix 2 Right recursion


A right recursive rule for an integer is:


integer: digit integer

| digit ;


The second alternative acts to terminate the recursion. As it stands, this rule is illegal for Dante because both alternatives begin with the same type. For Dante this rule must be re-written as:


integer: digit [ integer];


This is legal and correct Dante, but is inferior to the iterative form:


integer: digit < digit >;


This is not surprising since Dante favors iteration over recursion. The reason that the right recursive form requires the optional operators is simple. Once the last digit of the integer is processed the call to integer will return failure. This will end the recursion as required. But when a second member of a sequence fails an error is generated. The option operator prevents the error occurrence. Sometimes it is not necessary to use the option operator if the termination of the recursion will not generate an error. An example is the lexical rule par_lex_bstring.dan in the lib directory. All this complication is avoided by using the iterative form when possible.