Analyses of Deterministic Parsing Algorithms

This paper describes an approach for determining
the minimum, maximum, and average times to 
parse sentences acceptable by a deterministic parser.
 These quantities are presented in the form of 
symbolic formulas, called time-formulas.  The variables
in these formulas represent not only the length 
of the input string but also the time to perform elementary
operations such as pushing, popping, subscripting, 
iterating, etc.  By binding to the  variables actual numerical
values corresponding to a given compiler-machine 
configuration, one can determine the execution time
for that configuration.  Time-formulas are derived 
by examining the grammar rules and the program representing
the algorithm one wishes to analyze.  The 
approach is described by using a specific grammar that defines
simple arithmetic expressions.  Two deterministic
parsers are analyzed: a top-down recursive descent
LL(1) parser, and a bottom-up SLR(1) parser.  The 
paper provides estimates for the relative efficiencies
of the two parsers.  The estimates applicable 
to a specific machine, the PDP-10, are presented and
substantiated buy benchmarks.  Finally, the paper 
illustrates the proposed approach by applying it to
the analyses of parsers for a simple programming 
language.  

CACM June, 1978

Cohen, J.
Roth, M.

Syntactic analysis, analysis of algorithms,top-down
and bottom-up parsing, relative efficiencies.

4.12 5.23 5.24 5.25 5.7

CA780603 DH February 26, 1979  12:32 PM

1350	4	3094
1399	4	3094
1659	4	3094
1768	4	3094
1781	4	3094
1945	4	3094
2110	4	3094
2719	4	3094
2733	4	3094
2986	4	3094
3093	4	3094
3094	4	3094
3094	4	3094
3094	4	3094
1265	5	3094
2179	5	3094
2645	5	3094
3094	5	3094
3094	5	3094
3094	5	3094