<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

Published Online: Jun 12, 2023

Page range: 34 - 53

Received: Nov 16, 2022

Accepted: Apr 18, 2023

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

Keywords
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

Published Online: Jun 12, 2023

Page range: 34 - 53

Received: Nov 16, 2022

Accepted: Apr 18, 2023

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

KeywordsParsing 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.

Keywords
Parsing algorithm, tunnel parsing, ambiguous grammars, ambiguity, determinism