Premium
The parser generating system PGS
Author(s) -
Klein E.,
Martin M.
Publication year - 1989
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380191102
Subject(s) - computer science , lr parser , parsing , programming language , parsing expression grammar , top down parsing , parser combinator , pascal (unit) , top down parsing language , rule based machine translation , natural language processing , syntax error , artificial intelligence , generator (circuit theory) , bottom up parsing , context free grammar , abstract syntax tree , l attributed grammar , power (physics) , physics , quantum mechanics
PGS is a parser generating system accepting LALR(1) and related grammars in extended BNF notation and producing parsers based on table‐driven stack automata. To enable syntax‐directed translation, semantic actions can be attached to rules of the input grammar. An attribution mechanism allows the transfer of information between rules. The generated parsers have an automatic error recovery which can be tailored to satisfy specific needs of the language to be accepted. PGS generates parsers written in Pascal, Modula‐2, C or Ada. Compared with existing systems, e.g. YACC 1 , a parser generated by PGS is twice as fast and the parse tables require 25 per cent less storage. This paper gives a survey of algorithms involved in the generator and the generated parsers, and compares them with algorithms used in other systems. In detail, it compares several parse‐table representations and their implications for space and time efficiency of the generated parsers.