Publication detail

Comparison of Classical and Lazy Approach in SCG Compiler

JIRÁK, O. KOLÁŘ, D.

Original Title

Comparison of Classical and Lazy Approach in SCG Compiler

English Title

Comparison of Classical and Lazy Approach in SCG Compiler

Type

conference paper

Language

en

Original Abstract

The existing parsing methods of scattered context grammar usually expand nonterminals deeply in the pushdown. This expansion is implemented by using either a linked list, or some kind of an auxiliary pushdown. This paper describes the parsing algorithm of an LL(1)scattered context grammar. The given algorithm merges two principles together. The first approach is a table-driven parsing method commonly used for parsing of the context-free grammars. The second is a delayed execution used in functional programming. The main part of this paper is a proof of equivalence between the common principle (the whole rule is applied at once) and our approach (execution of the rules is delayed). Therefore, this approach works with the pushdown top only. In the most cases, the second approach is faster than the first one. Finally, the future work is discussed. 

English abstract

The existing parsing methods of scattered context grammar usually expand nonterminals deeply in the pushdown. This expansion is implemented by using either a linked list, or some kind of an auxiliary pushdown. This paper describes the parsing algorithm of an LL(1)scattered context grammar. The given algorithm merges two principles together. The first approach is a table-driven parsing method commonly used for parsing of the context-free grammars. The second is a delayed execution used in functional programming. The main part of this paper is a proof of equivalence between the common principle (the whole rule is applied at once) and our approach (execution of the rules is delayed). Therefore, this approach works with the pushdown top only. In the most cases, the second approach is faster than the first one. Finally, the future work is discussed. 

Keywords

SCG, delayed execution, lazy functions, PDA

RIV year

2011

Released

22.09.2011

Publisher

American Institute of Physics

Location

Halkidiki

ISBN

978-0-7354-0956-9

Book

NUMERICAL ANALYSIS AND APPLIED MATHEMATICS ICNAAM 2011: International Conference on Numerical Analysis and Applied Mathematics

Edition

NEUVEDEN

Edition number

NEUVEDEN

Pages from

873

Pages to

876

Pages count

4

URL

Documents

BibTex


@inproceedings{BUT76286,
  author="Ota {Jirák} and Dušan {Kolář}",
  title="Comparison of Classical and Lazy Approach in SCG Compiler",
  annote="The existing parsing methods of scattered context grammar usually expand
nonterminals deeply in the pushdown. This expansion is implemented by
using either a linked list, or some kind of an auxiliary pushdown. This paper
describes the parsing algorithm of an LL(1)scattered context grammar. The given
algorithm merges two principles together. The first approach is a table-driven
parsing method commonly used for parsing of the context-free grammars. The second
is a delayed execution used in functional programming. The main part of this
paper is a proof of equivalence between the common principle (the whole rule is
applied at once) and our approach (execution of the rules is delayed). Therefore,
this approach works with the pushdown top only. In the most cases, the second
approach is faster than the first one. Finally, the future work is discussed. ",
  address="American Institute of Physics",
  booktitle="NUMERICAL ANALYSIS AND APPLIED MATHEMATICS ICNAAM 2011: International Conference on Numerical Analysis and Applied Mathematics",
  chapter="76286",
  edition="NEUVEDEN",
  howpublished="electronic, physical medium",
  institution="American Institute of Physics",
  number="1",
  year="2011",
  month="september",
  pages="873--876",
  publisher="American Institute of Physics",
  type="conference paper"
}