Locating free positions in LR(k) grammars

Shih Ting Ouyang*, Pei Chi Wu, Feng-Jian Wang

*Corresponding author for this work

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

LR(k) is the most general category of linear-time parsing. Before a symbol is recognized in LR parsing, it is difficult to invoke the semantic action associated with the symbol. Adding semantic actions to an LR(k) grammar may result in a non-LR(k) grammar. There are two straightforward approaches adopted by practitioners of parser generators. The first approach is to delay all semantic actions until the whole parse tree is constructed. The second is to add semantic actions to the grammar by chance. This paper presents an efficient algorithm for finding positions (called free positions) that can freely put semantic actions into an LR(k) grammar. The speedups of our method range from 2.23 to 15.50 times for the eight tested grammars.

Original languageEnglish
Pages (from-to)411-423
Number of pages13
JournalJournal of Information Science and Engineering
Volume18
Issue number3
DOIs
StatePublished - 1 May 2002

Keywords

  • Free positions
  • LR(k) grammars
  • Parse tree
  • Parser generators
  • Semantic actions

Fingerprint Dive into the research topics of 'Locating free positions in LR(k) grammars'. Together they form a unique fingerprint.

  • Cite this