- Author:
- F. L. Deremer
A context-free syntactical translator (CFST) is a machine which defines a translation from one context-free language to another. A transduction grammar is a formal system based on a context-free grammar and it specifies a context-free syntactical translation. A simple suffix transduction grammar based on a context-free grammar which is LR(k) specifies a translation which can be defined by a deterministic push-down automation (DPDA). A method is presented for automatically constructing CFSTs (DPDAs) from those simple suffix transduction grammars which are based on the LR(k) grammars. The method is developed by first considering grammatical analysis from the string-manipulation viewpoint, then converting the resulting string-manipulation.
Cited By
- Jia X, Kumar A and Tan G (2023). A Derivative-based Parser Generator for Visibly Pushdown Grammars, ACM Transactions on Programming Languages and Systems, 45:2, (1-68), Online publication date: 30-Jun-2023.
- Handzhiyski N and Somova E (2022). Tunnel Parsing with the Token’s Lexeme, Cybernetics and Information Technologies, 22:2, (125-144), Online publication date: 1-Jun-2022.
- Strandh R A modern implementation of the LOOP macro Proceedings of the 9th European Lisp Symposium on European Lisp Symposium, (49-55)
- Might M, Darais D and Spiewak D Parsing with derivatives Proceedings of the 16th ACM SIGPLAN international conference on Functional programming, (189-195)
- Might M, Darais D and Spiewak D (2011). Parsing with derivatives, ACM SIGPLAN Notices, 46:9, (189-195), Online publication date: 18-Sep-2011.
- Berwick R and Weinberg A Syntactic constraints and efficient parsability Proceedings of the 21st annual meeting on Association for Computational Linguistics, (119-122)
- Sager T On the use of extended grammars Proceedings of the 20th annual ACM Southeast Regional Conference, (246-252)
- LaLonde W On directly constructing LR(k) parsers without chain reductions Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, (127-133)
- Bauer F, De Remer F, Griffiths M, Hill U, Horning J, Koster C, McKeeman W, Poole P, Waite W, Eickel J, Goos G and Hartmanis J (1974). Compiler construction, 10.5555/1102008, Online publication date: 1-Jan-1974.
- Pager D The lane tracing algorithm for constructing LR(k) parsers Proceedings of the fifth annual ACM symposium on Theory of computing, (172-181)
- DeRemer F (1971). Simple LR(k) grammars, Communications of the ACM, 14:7, (453-460), Online publication date: 1-Jul-1971.
- Wise D Domolki's algorithm applied to generalized overlap resolvable grammars Proceedings of the third annual ACM symposium on Theory of computing, (171-184)
- Aho A and Ullman J The care and feeding of LR(k) grammars Proceedings of the third annual ACM symposium on Theory of computing, (159-170)
- Hayashi T On the construction of LR(k) analyzers Proceedings of the 1971 26th annual conference, (538-553)
Recommendations
LR parsers for natural languages
ACL '84/COLING '84: Proceedings of the 10th International Conference on Computational Linguistics and 22nd annual meeting on Association for Computational LinguisticsMLR, an extended LR parser, is introduced, and its application to natural language parsing is discussed. An LR parser is a shift-reduce parser which is deterministically guided by a parsing table. A parsing table can be obtained automatically from a ...
LL and LR translators need k>1 lookahead
Language translation is a harder and more important problem than language recognition. In particular, programmers implement translators not recognizers. Yet too often, translation is equated with the simpler task of syntactic parsing. This misconception ...
A backtracking LR algorithm for parsing ambiguous context-dependent languages
CASCON '06: Proceedings of the 2006 conference of the Center for Advanced Studies on Collaborative researchParsing context-dependent computer languages requires an ability to maintain and query data structures while parsing for the purpose of influencing the parse. Parsing ambiguous computer languages requires an ability to generate a parser for arbitrary ...