Search

Schmeiser and Barnard described a method for producing the left parse at the end of the bottom-up parsing process. We improve their method in the sense that the left parse is actually produced during the bottom-up parsing process (i.e., with considerably less delay).

An adaptation of the standard LR(1) and LALR(1) parsing algorithm is described such that a top-down parse order is produced rather than the standard bottom-up order.

Not all implementations of LR parsers are created equal. The differences become apparent when the language that each LR state recognizes is considered.

Operator-precedence parsing [1] is an important parsing algorithm for expression-like languages. It is fast and uses very compact parsing tables. The algorithm is not correct for all grammars. In some cases, both valid and invalid sentences will be accepted by the parser. Unfortunately, this occurs for the expression grammars that are used in most programming languages. It is possible to augment the algorithm in an ad-hoc way, but the correctness of the parser may then be difficult to establish. As an alternative to ad-hoc methods, Henderson and Levy [2] proposed an extended algorithm that works correctly for a larger class of grammars. The extended algorithm appears to work correctly for typical expression grammars, but there are still grammars for which it accepts invalid sentences, too. There have been attempts [3,5] to find conditions on the grammar that will ensure correctness of the constructed parser, but these conditions are difficult to formulate and it is unclear whether they are correct. Recently, Ruzicka [4] has developed an alternative approach to ensuring correctness of an operator-precedence parser. His method is to first construct the parser and then to verify that the language accepted by the parser is the same language

We show that languages generated by LL(1) grammars can be parsed in logarithmic time on the Connection Machine. The algorithm extends a lexing algorithm of Hillis et al. and demonstrates that the widely-held supposition that parsing is inherently linear is false.

A recursive parsing algorithm is presented which is the analogue to a bottom-up parsing strategy of what is the recursive descent parsing algorithm to a dop-down parsing strategy.