Parsing algorithms for grammars with regulated rewriting
In recent papers [4, 5, 8, 11] Petri net controlled grammars have been introduced and investigated. It was shown that various regulated grammars such as random context, matrix, vector, valence grammars, etc., resulted from enriching context-free grammars with additional mechanisms can be unified int...
| Main Authors: | , , , |
|---|---|
| Format: | Proceeding Paper |
| Language: | English English |
| Published: |
2011
|
| Subjects: | |
| Online Access: | http://irep.iium.edu.my/27325/ http://irep.iium.edu.my/27325/1/Parsing_Algorithms_for_Grammars_with_Regulated_Rewriting.pdf http://irep.iium.edu.my/27325/4/ACRE.pdf |
| _version_ | 1848779800787812352 |
|---|---|
| author | Turaev, Sherzod Othman, Mohamed Selamat, Mohd Hasan Krassovitskiy, Alexander |
| author_facet | Turaev, Sherzod Othman, Mohamed Selamat, Mohd Hasan Krassovitskiy, Alexander |
| author_sort | Turaev, Sherzod |
| building | IIUM Repository |
| collection | Online Access |
| description | In recent papers [4, 5, 8, 11] Petri net controlled grammars have been introduced and investigated. It was shown that various regulated grammars such as random context, matrix, vector, valence grammars, etc., resulted from enriching context-free grammars with additional mechanisms can be unified into the Petri net formalism, i.e., a grammar and its control can be represented by a Petri net. This unification allows approaching the membership (parsing) problem in formal language theory in the new point of view: instead of a usual derivation tree, one can use a Petri net derivation tree in which the control mechanism is also considered as a part of the tree. In this paper, we show that the parsing problem for regulated grammars can be solved by means of Petri net derivation trees constructed using the net unfolding. Moreover, we present a parsing algorithm for the deterministic restriction of Petri net controlled grammars based on the well-known Earley parsing algorithm. |
| first_indexed | 2025-11-14T15:23:32Z |
| format | Proceeding Paper |
| id | iium-27325 |
| institution | International Islamic University Malaysia |
| institution_category | Local University |
| language | English English |
| last_indexed | 2025-11-14T15:23:32Z |
| publishDate | 2011 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | iium-273252015-09-17T04:18:17Z http://irep.iium.edu.my/27325/ Parsing algorithms for grammars with regulated rewriting Turaev, Sherzod Othman, Mohamed Selamat, Mohd Hasan Krassovitskiy, Alexander QA Mathematics QA75 Electronic computers. Computer science In recent papers [4, 5, 8, 11] Petri net controlled grammars have been introduced and investigated. It was shown that various regulated grammars such as random context, matrix, vector, valence grammars, etc., resulted from enriching context-free grammars with additional mechanisms can be unified into the Petri net formalism, i.e., a grammar and its control can be represented by a Petri net. This unification allows approaching the membership (parsing) problem in formal language theory in the new point of view: instead of a usual derivation tree, one can use a Petri net derivation tree in which the control mechanism is also considered as a part of the tree. In this paper, we show that the parsing problem for regulated grammars can be solved by means of Petri net derivation trees constructed using the net unfolding. Moreover, we present a parsing algorithm for the deterministic restriction of Petri net controlled grammars based on the well-known Earley parsing algorithm. 2011 Proceeding Paper PeerReviewed application/pdf en http://irep.iium.edu.my/27325/1/Parsing_Algorithms_for_Grammars_with_Regulated_Rewriting.pdf application/pdf en http://irep.iium.edu.my/27325/4/ACRE.pdf Turaev, Sherzod and Othman, Mohamed and Selamat, Mohd Hasan and Krassovitskiy, Alexander (2011) Parsing algorithms for grammars with regulated rewriting. In: 11th WSEAS International Conference on Applied Computer Science (ACS '11), 3-5 October 2011, Penang. http://www.wseas.us/books/2011/Penang/ACRE.pdf |
| spellingShingle | QA Mathematics QA75 Electronic computers. Computer science Turaev, Sherzod Othman, Mohamed Selamat, Mohd Hasan Krassovitskiy, Alexander Parsing algorithms for grammars with regulated rewriting |
| title | Parsing algorithms for grammars with regulated rewriting |
| title_full | Parsing algorithms for grammars with regulated rewriting |
| title_fullStr | Parsing algorithms for grammars with regulated rewriting |
| title_full_unstemmed | Parsing algorithms for grammars with regulated rewriting |
| title_short | Parsing algorithms for grammars with regulated rewriting |
| title_sort | parsing algorithms for grammars with regulated rewriting |
| topic | QA Mathematics QA75 Electronic computers. Computer science |
| url | http://irep.iium.edu.my/27325/ http://irep.iium.edu.my/27325/ http://irep.iium.edu.my/27325/1/Parsing_Algorithms_for_Grammars_with_Regulated_Rewriting.pdf http://irep.iium.edu.my/27325/4/ACRE.pdf |