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

Full description

Bibliographic Details
Main Authors:	Turaev, Sherzod, Othman, Mohamed, Selamat, Mohd Hasan, Krassovitskiy, Alexander
Format:	Conference or Workshop Item
Language:	English English
Published:	2011
Subjects:	QA Mathematics QA75 Electronic computers. Computer science
Online Access:	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

id	iium-27325
recordtype	eprints
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 Conference or Workshop Item 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
repository_type	Digital Repository
institution_category	Local University
institution	International Islamic University Malaysia
building	IIUM Repository
collection	Online Access
language	English English
topic	QA Mathematics QA75 Electronic computers. Computer science
spellingShingle	QA Mathematics QA75 Electronic computers. Computer science Turaev, Sherzod Othman, Mohamed Selamat, Mohd Hasan Krassovitskiy, Alexander Parsing algorithms for grammars with regulated rewriting
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.
format	Conference or Workshop Item
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
title	Parsing algorithms for grammars with regulated rewriting
title_short	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_sort	parsing algorithms for grammars with regulated rewriting
publishDate	2011
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
first_indexed	2023-09-18T20:40:37Z
last_indexed	2023-09-18T20:40:37Z
_version_	1777409340076982272

Parsing algorithms for grammars with regulated rewriting

Similar Items