English   español  
Por favor, use este identificador para citar o enlazar a este item: http://hdl.handle.net/10261/127934
Compartir / Impacto:
Estadísticas
Add this article to your Mendeley library MendeleyBASE
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Título

Parsing systems for regular and context-free languages

AutorSteels, Luc
Fecha de publicación1975
EditorUniversity of Antwerp (Belgium)
CitaciónAntwerp Papers in Linguistics 1: (1975)
ResumenIn this paper we approach the following problem: Given an arbitrary language describing device (e.g. a grammar), construct an algorithm which computes structural information for an arbitrary string of the. language described by this device. Algorithms performing this task are called parsers and the problem itself is known as the 'recognition' or 'parsing' problem. In the first part three devices accepting the set of regular or type 3 languages are presented: transition networks, finite state machines and regular grammars. Then parsers are constructed with these systems as data. Basically a parser works an n-tuples (called tasks) containing all sorts of information, e.g. what symbol should be read in the inputstring, which rule can be applied, etc... Starting from a given initial task, new tasks are constructed from previous tasks by means of a recursive function. The execution of the function involves scanning the inputstring and consulting the grammar. After a finite number of steps, no more tasks can be created and from the set of tasks produced during the computation structural information can be filtered out. In the second part of the paper three devices accepting the set of contextfree or type 2 languages are presented: recursive transition networks, pushdown automata and context-free grammars. Then parsers are constructed for these systems with the same basic strategy. Emphasis is laid on the construction of a fundamental theoretical framework rather than the description of sophisticated parsers and their implementations.
Versión del editorhttp://www.clips.ua.ac.be/archive/parsing-systems-for-regular-and-context-free-languages
URIhttp://hdl.handle.net/10261/127934
Aparece en las colecciones: (IBE) Artículos
Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
Parsing Systems.pdf808,03 kBAdobe PDFVista previa
Visualizar/Abrir
Mostrar el registro completo
 


NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.