<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>The article proposes an addition to the tunnel parsing algorithm that enables it to parse grammars having countable repetitions and configurations of grammar elements generating empty words without refactoring the grammar. The equivalency of trees built by the use of ambiguous grammar is discussed. The class of the ε-ambiguous grammars is defined as a subclass of the ambiguous grammars relative to these trees. The ε-deterministic grammars are then defined as a subclass of the ε-ambiguous grammars. A technique for linearly parsing on the basis of non-left recursive ε-deterministic grammars with the tunnel parsing algorithm is shown.</p>
</abstract>

The article proposes an addition to the tunnel parsing algorithm that enables it to parse grammars having countable repetitions and configurations of grammar elements generating empty words without refactoring the grammar. The equivalency of trees built by the use of ambiguous grammar is discussed. The class of the ε-ambiguous grammars is defined as a subclass of the ambiguous grammars relative to these trees. The ε-deterministic grammars are then defined as a subclass of the ε-ambiguous grammars. A technique for linearly parsing on the basis of non-left recursive ε-deterministic grammars with the tunnel parsing algorithm is shown.

Tunnel Parsing with Ambiguous Grammars

University of Plovdiv “Paisii Hilendarski”

Cybernetics and Information Technologies

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

{"article-title":"Tunnel Parsing with Ambiguous Grammars"}

The article proposes an addition to the tunnel parsing algorithm that enables it to parse grammars having countable repetitions and configurations of grammar...

Tunnel Parsing with Ambiguous Grammars

Publicado en línea: 12 jun 2023

Páginas: 34 - 53

Recibido: 16 nov 2022

Aceptado: 18 abr 2023

DOI: https://doi.org/10.2478/cait-2023-0012

Palabras clave
Parsing algorithm, tunnel parsing, ambiguous grammars, ambiguity, determinism

© 2023 Nikolay Handzhiyski et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Tunnel Parsing with Ambiguous Grammars

Publicado en línea: 12 jun 2023

Páginas: 34 - 53

Recibido: 16 nov 2022

Aceptado: 18 abr 2023

DOI: https://doi.org/10.2478/cait-2023-0012

Palabras claveParsing algorithm, tunnel parsing, ambiguous grammars, ambiguity, determinism

© 2023 Nikolay Handzhiyski et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Palabras clave
Parsing algorithm, tunnel parsing, ambiguous grammars, ambiguity, determinism