On LL-to-LR covering languages = LL에서 LR로의 커버링 언어에 관한 연구

As formal approaches to characterize LL languages, the restricted LR grammars, PLR and κ-transformable grammars have been characterized by suggesting left-to-right covering transformations. The κ-transformable grammar was conjectured as the upper bound of the grammars which have such covering transformations. The previous transformation of κ-transformable grammars, however, requires construction of intricate multiple stack machine. Moreover, κ-transformable-ness of a grammar is determined by trial-and-error construction of cycle-free multiple stack machines. On the other hand, PLR grammar is known as a well-characterized subgrammar of κ-transformable grammar. The claim, however, is not obvious since there is no proof about the relationship between PLR and κ-transformable grammars. First, a grammatical transformation and a grammatical characterization of κ-transformable grammar are suggested. They do not require any construction of multiple stack machine. Second, it is shown that PLR grammar class is not a subclass of κ-transformable grammar class. Third, an extended LL-to-LR covering transformation is suggested. The transformable grammar class includes PLR and κ-transformable grammar strictly, and it is called extended PLR. The new transformation needs a single deterministic process compared to the teial-and-error processes of κ-transformable grammars. Fourth, an LR parser with predetermined reduction goals is suggested. In the LR parser, each LR state has the goal and the suffix of the stack string such that the suffix stack string and some prefix of the remaining input string will be certainly reduced into the goal. Some applications of the predictive LR parser are shown.
Advisors
Choe, Kwang-Mooresearcher최광무researcher
Publisher
한국과학기술원
Issue Date
2000
Identifier
157667/325007 / 000925567
Language
eng
Description

학위논문(박사) - 한국과학기술원 : 전산학전공, 2000.2, [ iii, 74 p. ]

Keywords

lr grammars; parsing; compiler; ll grammars; LL 문법; LR 문법; 파싱; 컴파일러

URI
http://hdl.handle.net/10203/33152
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=157667&flag=t
Appears in Collection
CS-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.
  • Hit : 184
  • Download : 0
  • Cited 0 times in thomson ci

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0