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