# Questions tagged [parsers]

Questions about algorithms that decide whether a given string belongs to a fixed formal language.

344 questions
Filter by
Sorted by
Tagged with
54 views

### Best Approach To Parse Human Readable Text To Machine Readable (CSV)

I am attempting to parse a large amount of text that cannot be readily used by other software due to the human readable design. However, each "section" of the text has the same format. By "section", I ...
2k views

### Dangling else problem

I was reading a book about compiler design, then in the CFG section, they introduced the dangling-else problem. They offered to match the the else with the last <...
82 views

### Examples of context-free grammars with worst-case complexity

What are some examples of context-free grammars that necessarily trigger cubic worst-case complexity for GLR parsers? I have seen a mention of the example S $\rightarrow$ SSS | SS | "a" but I would ...
290 views

### How do we evaluate semantic actions in L attributed SDT?

I came across following problem: $S→ER$ $R→∗E\{print(′∗′);\}R∣ε$ $E→F+E\{print(′+′);\}∣F$ $F→(S)∣id\{print(id.value);\}$ Here $id$ is a token that represents an integer and $id.value$ ...
247 views

### Not getting the clear picture of Goto actions , reduce and shift actions in SLR Parsing

I am going through the following lecture notes on LR parsing : https://www3.nd.edu/~dthain/courses/cse40243/fall2016/chapter4b.pdf For the following grammar : The following LR automation has been ...
67 views

### Is there a way to efficiently parse this grammar?

Consider the following context-free grammar: $T \to (*) \mid (T*) \mid (*T) \mid (T*T)$ This effectively forms a notation for binary trees: A binary tree is a $*$, with optional children on either ...
604 views

### Number of nodes of a parse tree when the Grammar is in CNF?

There happened to be a following question - In any Chomsky Normal Form grammar $G$, how many nodes will all parse trees for terminal strings of length $n>0$ generated by G have? I tried for ...
41 views

The book I am learning about compilers from states that $M \to \alpha N \beta$ will generate a constraint that $\mathrm{FOLLOW}(M)$ is contained in $\mathrm{FOLLOW}(N)$ when $\beta$ is nullable. This ...
399 views

### Tokenization Problem

Yes, this is a quiz question. It's from a self-paced course, but the answer just isn't correct to me no matter how I look at it. There isn't really an active community to consult. My Regular ...
378 views

5k views

### LL(1) parsing table construction

i have the following CFG E -> ABC A-> a|Cb|epsilon B-> c|xA|epsilon C-> y|z and the First of the Non-Terminal : ...
500 views

64 views

### Is it possible to transform this grammar into LL(1)?

This is the original grammar: S -> ABe A -> ab | a | ϵ B -> b I did try left factoring and this is what I got: ...