A One-Gap Parsing with Extended PLR(1) Grammars 


Vol. 42,  No. 3, pp. 361-366, Mar.  2015


PDF

  Abstract

Gap parsing is an algorithm for parsing incomplete input strings which include some gaps. Gap parsing is different from conventional parsing, and as known results, one-gap parsing algorithms for arbitrary context-free grammar and LL(1) grammar have O(n³) and O(n²) time complexity, respectively.
This paper presents a one-gap parsing algorithm for extended PLR(1) grammars. Extended PLR(1) grammars are the class of grammars smaller than LR(1) but much larger than LL(1). The one-gap parsing algorithm of the grammar class is shown to have the time complexity of O(n²), which is equal to the complexity of one-gap parsing algorithms for LL(1) grammars.


  Statistics
Cumulative Counts from November, 2022
Multiple requests among the same browser session are counted as one view. If you mouse over a chart, the values of data points will be shown.


  Cite this article

[IEEE Style]

G. Lee, "A One-Gap Parsing with Extended PLR(1) Grammars," Journal of KIISE, JOK, vol. 42, no. 3, pp. 361-366, 2015. DOI: .


[ACM Style]

Gyung-Ok Lee. 2015. A One-Gap Parsing with Extended PLR(1) Grammars. Journal of KIISE, JOK, 42, 3, (2015), 361-366. DOI: .


[KCI Style]

이경옥, "확장된 PLR(1) 문법에 대한 단일 틈 파싱," 한국정보과학회 논문지, 제42권, 제3호, 361~366쪽, 2015. DOI: .


[Endnote/Zotero/Mendeley (RIS)]  Download


[BibTeX]  Download



Search




Journal of KIISE

  • ISSN : 2383-630X(Print)
  • ISSN : 2383-6296(Electronic)
  • KCI Accredited Journal

Editorial Office

  • Tel. +82-2-588-9240
  • Fax. +82-2-521-1352
  • E-mail. chwoo@kiise.or.kr