Modestas Valauskas

# Testcase: unnecessary LR(1) splits [This](https://mdaines.github.io/grammophone/?s=UyAtPiBhIFggYSB8IGIgWCBiIHwgYSBZIGIgfCBiIFkgYS4KWCAtPiBjICJYJyIuClkgLT4gYyAiWSciLgoiWCciIC0+IGMuCiJZJyIgLT4gYy4=) grammar demonstrates a source of inefficiency in the automaton of the standard LR(1) construction. Looking at the LR(1) automaton, I think that state 13...

Superseded by https://github.com/mdaines/grammophone/issues/26#issuecomment-1657506763 --- # Transformation: Recursion Scheme Fusion [This](https://mdaines.github.io/grammophone/?s=aGVhZGVyIC0+IHR5cGVfbmFtZSBpZCAnKCcgcGFyYW1zICcpJyB8IHR5cGVfbmFtZSBpZCAnKCcgJyknLgp0eXBlX25hbWUgLT4gaWQgfCBtb3JlX2NvbXBsZXhfdHlwZV9kZXNjcmlwdGlvbnMuCiMgTFIoMikKIyBwYXJhbXMgIC0+IHBhcmFtIHwgcGFyYW1zICcsJyBwYXJhbS4KIyBwYXJhbSAgIC0+IHR5cGVfbmFtZSBpZHMuCiMgaWRzICAgICAtPiBpZCB8IGlkcyAnLCcgaWQuCiMgTFIoMSkKcGFyYW1zICAtPiB0eXBlX25hbWUgaWQgfCBwYXJhbXMgJywnIHR5cGVfbmFtZSBpZCB8IHBhcmFtcyAnLCcgaWQu) grammar is LR(2), but can be easily converted to LR(1) by a procedure that heavily reminds me of [recursion scheme](https://blog.sumtypeofway.com/posts/introduction-to-recursion-schemes.html)...

# Testcase: NQLALR guard Here are two other interesting grammars: When implementing an LALR parser using the Deremer and Pennello relation-based algorithm, it is easy to implement something that is...

# Testcase: LALR correctness The following paper discusses an incorrect oversimplification that one can make while implementing their algorithm. [Efficient Computation of LALR(1) Look-Ahead Sets, Frank DeRemer & Thomas Pennello](https://dl.acm.org/doi/pdf/10.1145/69622.357187)...

# Testcase: LALR(2) The following paper discusses a grammar that is "almost" LALR(1). It has 9 inadequate states under LR(0). 8 of them can be resolved using LALR(1) and there's...

# Metric: Includes Theorem DeRemer & Pennello conjectured that if the "includes" relation of their LALR(1) construction algorithm contains a nontrivial SCC, then the grammar can't be LR(k) for any...

# Transformation: Recursion Scheme Fusion The [PhD Thesis by Philippe Charles on LALR(k) parsing and automatic error recovery](https://jikes.sourceforge.net/documents/thesis.pdf) discusses the following three grammars extensively (Figure 3.1, Page 31). They all...

# Metric: Read Theorem In [Efficient Computation of LALR(1) Look-Ahead Sets, Frank DeRemer & Thomas Pennello](https://dl.acm.org/doi/pdf/10.1145/69622.357187), the authors prove that if there's a nontrivial SCC in the reads relation of...

# Transformation: (Right-)CPS [The following grammar](https://mdaines.github.io/grammophone/?s=RmllbGQgLT4gUyBFLgpGaWVsZCAtPiBFIEUuClMgLT4gcy4KUyAtPiAu) is presented in [the following paper](https://arxiv.org/pdf/2209.08383.pdf) that was published alongside langcc (cf. page 5 bullet 4): ``` Field -> S E. Field -> E...

# Metric: Context splitting only resolves R/R conflicts In his [dissertation](https://hyacc.sourceforge.net/files/chenx_dissertation.pdf) on LR parsing (page 94, first bullet, third paragraph), Xin Chen claims that it is widely known that only...