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) [antigua denominación].


Título: A Syntactic Approach to Macro-Grammars for Context-Free Languages
  • Nuche Bascón, Jaime
  • Nogueira Iglesias, Pablo
Tipo de Documento: Proyecto Fin de Carrera/Grado
Fecha: Julio 2009
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Lenguajes y Sistemas Informáticos e Ingeniería del Software
Licencias Creative Commons: Reconocimiento - No comercial - Compartir igual

Texto completo

Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (315kB) | Vista Previa


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.

Más información

ID de Registro: 1828
Identificador DC: http://oa.upm.es/1828/
Identificador OAI: oai:oa.upm.es:1828
Depositado por: Archivo Digital UPM
Depositado el: 24 Sep 2009 12:22
Ultima Modificación: 20 Abr 2016 07:02
  • GEO_UP4
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • InvestigaM
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM