English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/127934
logo share SHARE   Add this article to your Mendeley library MendeleyBASE
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:


Parsing systems for regular and context-free languages

AuthorsSteels, Luc
Issue Date1975
PublisherUniversity of Antwerp (Belgium)
CitationAntwerp Papers in Linguistics 1: (1975)
AbstractIn 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.
Publisher version (URL)http://www.clips.ua.ac.be/archive/parsing-systems-for-regular-and-context-free-languages
Appears in Collections:(IBE) Artículos
Files in This Item:
File Description SizeFormat 
Parsing Systems.pdf808,03 kBAdobe PDFThumbnail
Show full item record
Review this work

WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.