CS [45]12[01] Spring 2023

So far we've been looking at top-down parsing. A top-down parser is limited in the grammars it can handle because it must be able to commit to predicted productions high in the parse tree based on relatively little information. For example, it must be able to choose the correct production from the start symbol based on the first token in the input. This limitation motivates bottom-up parsing, in which the parser can choose productions after seeing more input. For example, bottom-up parsers can handle left-recursive productions whereas top-down parsers cannot. In fact, bottom-up parsers work best when productions are left-recursive, although they can handle right-recursive productions too. In the following figure, the shaded areas represent the part of the parse tree that must be predicted when some of the input has been read. An powerful yet ingeniously simple bottom-up parser is that due to Jay Earley. It can parse all context-free grammars, including ambiguous ones. Its worst-case ti

saved by

• Owen Oertell