LR Formalisms as Abstract Interpretations of Grammar Semantics

Seunghwan O  Kwang-Moo CHOE  

IEICE TRANSACTIONS on Information and Systems   Vol.E89-D   No.12   pp.2924-2932
Publication Date: 2006/12/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e89-d.12.2924
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Automata and Formal Language Theory
formal language,  LR parsing,  formal semantics,  abstract interpretation,  

Full Text: PDF>>
Buy this Article

The concept of LR(k) validity is represented as an abstract interpretation of a refinement of the derivation semantics of a given grammar. Also the algorithm of LR(k) parsing is represented as an abstract interpretation of the refined semantics. Such representations of LR formalisms provide us with more intuitive and easier means by which to understand LR parsing.