A Syntactic Approach to Macro-Grammars for Context-Free Languages

Nuche Bascón, Jaime (2009). A Syntactic Approach to Macro-Grammars for Context-Free Languages. Proyecto Fin de Carrera / Trabajo Fin de Grado, Facultad de Informática (UPM).

Description

Title: A Syntactic Approach to Macro-Grammars for Context-Free Languages
Author/s:
  • Nuche Bascón, Jaime
Contributor/s:
  • Nogueira Iglesias, Pablo
Item Type: Final Project
Date: July 2009
Subjects:
Faculty: Facultad de Informática (UPM)
Department: Lenguajes y Sistemas Informáticos e Ingeniería del Software
Creative Commons Licenses: Recognition - Non commercial - Share

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (315kB) | Preview

Abstract

We commence this thesis by setting a backdrop for the work. In [HN05] Herranz and Nogueira introduced the MTP (More Than Parsing) tool. They designed MTP to be an automatic parser generator. Their main contribution consisted in a syntax formalism which avoids the burden of annotated grammars, an inconvenience present in most modern automatic parser generators, while at the same time supplying the parser with quality data structures. The syntax formalism they introduced, GONF(Generalized Object Normal Form), is similar to the well-known BNF formalism for describing context-free grammars; the grammars used at present to build parsers. GONF allows for the use of parameterized non-terminals in the description of grammars. However, it was necessary to prove that this extension did not cause the formalism to generate grammars not in the context-free class. GONF's parameterized non-terminals are simply macros, like those in regular programming languages. Grammars with macros have been studied in [Fis68, TN04, TN08]. It was proved in these works that macro-grammars can actually generate context-sensitive languages. They also introduce some attempts at limiting macrogrammars to generate only context-free languages, though results are not completely satisfactory and present some issues. Based on these works, I present a new formal framework for macro-grammars. I also provide a new characterization for macro-grammars and two di_erent practical restrictions which ensure a given macro-grammar remains within the context-free class boundaries. We can apply these restrictions to GONF or any other notation for macro-grammars.

More information

Item ID: 1828
DC Identifier: http://oa.upm.es/1828/
OAI Identifier: oai:oa.upm.es:1828
Deposited by: Archivo Digital UPM
Deposited on: 24 Sep 2009 12:22
Last Modified: 20 Apr 2016 07:02
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM