Parsing algorithms for grammars with regulated rewriting

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.

	PDF - Published Version Restricted to Registered users only Download (292kB) | Request a copy
	PDF (Parsing algorithms for grammars with regulated rewriting) Restricted to Registered users only Download (1MB) | Request a copy

Abstract

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.

Item Type:	Conference or Workshop Item (Full Paper)
Additional Information:	6846/27325
Subjects:	Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Kulliyyahs/Centres/Divisions/Institutes (Can select more than one option. Press CONTROL button):	Kulliyyah of Information and Communication Technology Kulliyyah of Information and Communication Technology
Depositing User:	Dr. Sherzod Turaev
Date Deposited:	14 Feb 2013 12:57
Last Modified:	17 Sep 2015 12:18
URI:	http://irep.iium.edu.my/id/eprint/27325

Actions (login required)

View Item