patternMinor
Streaming parsing algorithms
Viewed 0 times
parsingstreamingalgorithms
Problem
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?
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?
Solution
The first solution coming to mind is an extension of Brzozowski's derivatives as context-free grammars are closed under derivative operation with respect to a letter.
Here that question answered: https://cstheory.stackexchange.com/questions/3280/generalizations-of-brzozowskis-method-of-derivatives-of-regular-expressions-to
Here that question answered: https://cstheory.stackexchange.com/questions/3280/generalizations-of-brzozowskis-method-of-derivatives-of-regular-expressions-to
Context
StackExchange Computer Science Q#62527, answer score: 2
Revisions (0)
No revisions yet.