Recursive descent parsing for Boolean grammars |
| |
Authors: | Alexander Okhotin |
| |
Affiliation: | (1) Department of Mathematics, University of Turku, Turku, 20014, Finland;(2) Academy of Finland, Vilhonvuorenkatu 6, Helsinki, 00501, Finland |
| |
Abstract: | The recursive descent parsing method for the context-free grammars is extended for their generalization, Boolean grammars,
which include explicit set-theoretic operations in the formalism of rules and which are formally defined by language equations.
The algorithm is applicable to a subset of Boolean grammars. The complexity of a direct implementation varies between linear
and exponential, while memoization keeps it down to linear.
Supported by the Academy of Finland under grant 118540. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|