<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

Online veröffentlicht: 12. Juni 2023

Seitenbereich: 34 - 53

Eingereicht: 16. Nov. 2022

Akzeptiert: 18. Apr. 2023

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

Schlüsselwörter
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

Online veröffentlicht: 12. Juni 2023

Seitenbereich: 34 - 53

Eingereicht: 16. Nov. 2022

Akzeptiert: 18. Apr. 2023

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

SchlüsselwörterParsing 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.

Schlüsselwörter
Parsing algorithm, tunnel parsing, ambiguous grammars, ambiguity, determinism