<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

Publié en ligne: 12 juin 2023

Pages: 34 - 53

Reçu: 16 nov. 2022

Accepté: 18 avr. 2023

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

Mots clés
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

Publié en ligne: 12 juin 2023

Pages: 34 - 53

Reçu: 16 nov. 2022

Accepté: 18 avr. 2023

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

Mots clésParsing 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.

Mots clés
Parsing algorithm, tunnel parsing, ambiguous grammars, ambiguity, determinism