Frage

A parser is a procedure which decides if an input belongs to a certain language and produces a witness in the form of a parse tree.

Let a streaming parser be a parser which for any prefix $u$ can produce a partial parse tree corresponding to the productions that must be expanded to eventually accept any completion $uv$ of the prefix, for some completion $v$.

For example, if parsing the CFG $$ \begin{array}{lcl} S &\to& (a S+ b) \end{array} $$

then upon reading the prefix $aaa$, the streaming parser should report that any parse tree must consist of three top-level expansions of $S$.

Edit: I have two motivations for streaming parsing. The first is to provide a best-case constant bound on memory usage in the case where productions can always be resolved by a constant amount of lookahead. The second is to allow the consumer to lazily tear down the parse tree as the result is produced, e.g. by scheduling the execution of semantic actions associated with productions.

I am also interested in streaming parsing based on other foundations than context-free grammars, such as top-down parsing (parsing expression grammars, parser combinators, etc.).

Is there any existing work on such parsing algorithms?

Keine korrekte Lösung

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange
scroll top