Digital Library[ Search Result ]
An Earley Parser using Equi-LR Items
http://doi.org/10.5626/JOK.2024.51.8.685
Abstract The Earley parser is applicable to generalized grammars, including ambiguous ones, unlike the LR parser. As a result, the Earley parser has been widely used in fields such as natural language processing and image processing. However, the Earley parser has the drawback of higher time and space costs compared to the LR parser. This paper proposes an Equi-Earley parser that improves efficiency by modifying the items used in the original Earley parser. The Equi-Earley parser employs items composed of a prefix of a rule and a dot, in contrast to the Earley parser, which uses items composed of a rule and a dot, similar to LR items. Consequently, the number of items in a state of the Equi-Earley parser is reduced compared to that of the Earley parser. The Earley parser generates items during parsing, unlike the LR parser. Hence, the Equi-Earley parser has the advantage of reduced parsing time and memory space compared to the original Earley parser.
On Equi-LR automata
http://doi.org/10.5626/JOK.2021.48.3.352
LR parsing is a representative bottom-up parsing method, and LR automata have been used as the essential frame for the construction of LR parser. This paper defines an equivalence class of classical LR items, which is called Equi-LR class and defines Equi-LR automata by using Equi-LR class instead of classical LR items. This paper shows that Equi-LR automata have the advantage of reduced construction time over classical LR automata, and the size complexity of LR parser in the frame of Equi-LR automata is tighter compared with the frame of classical LR automata.
A Model of Probabilistic Parsing Automata
Probabilistic grammar is used in natural language processing, and the parse result of the grammar has to preserve the probability of the original grammar. As for the representative parsing method, LL parsing and LR parsing, the former preserves the probability information of the original grammar, but the latter does not. A characteristic of a probabilistic parsing automaton has been studied; but, currently, the generating model of probabilistic parsing automata has not been known. The paper provides a model of probabilistic parsing automata based on the single state parsing automata. The generated automaton preserves the probability of the original grammar, so it is not necessary to test whether or not the automaton is probabilistic parsing automaton; defining a probability function for the automaton is not required. Additionally, an efficient automaton can be constructed by choosing an appropriate parameter.
Application of Single-State Parsing Automata to LR Grammars
Single-state parsing automata have a characteristic such that the decision of an action depends only on the current state but not on the parsing history. The memory space and the parsing time of single-state parsing automata are less than the memory space and the parsing time of LR automata. However, the applicable grammar class of single-state parsing automata is less than that of LR automata. This paper provides extended single-state parsing automata, which are applicable to LR grammars. In the prior work, the special state, referred to as the cyclic state was not treated in the construction of single-state parsing automata, and hence, the applicable grammar class was less than LR grammars. The paper solves the problem of cyclic states by processing dynamic information depending on an input string. The proposed method expands the application of grammar class of single-state parsing automata to LR grammars.
A One-Gap Parsing with Extended PLR(1) Grammars
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.
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