Parsing algorithms for regulated grammars

Sherzod Turaev, Alexander Krassovitskiy, Mohamed Othman, Mohd Hasan Selamat

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

Petri nets, introduced by Carl Adam Petri [12] in 1962, provide a powerful mathematical formalism for describing and analyzing the flow of information and control in concurrent systems. Petri nets can successfully be used as control mechanisms for grammars, i.e., the generative devices of formal languages. In recent papers [4], [5], [9], [16] 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.

Original languageEnglish
Pages (from-to)748-756
Number of pages9
JournalInternational Journal of Mathematical Models and Methods in Applied Sciences
Volume6
Issue number6
Publication statusPublished - 2012
Externally publishedYes

Keywords

  • Formal languages
  • Parsing algorithms
  • Petri net controlled grammars
  • Petri nets
  • Regulated grammars

ASJC Scopus subject areas

  • Modelling and Simulation
  • Mathematical Physics
  • Computational Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Parsing algorithms for regulated grammars'. Together they form a unique fingerprint.

Cite this