Questions tagged [parsers]

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

Filter by
Sorted by
Tagged with
6
votes
2answers
184 views

Computing follow sets conservatively for a PEG grammar

Given a parsing expression grammar (PEG) grammar and the name of the start production, I would like to label each node with the set of characters that can follow it. I would be happy with a good ...
14
votes
2answers
3k views

Does the language of Regular Expressions need a push down automata to parse it?

I want to convert a user entered regular expression into an NFA so that I can then run the NFA against a string for matching purposes. What is the minimum machine that can be used to parse regular ...
0
votes
1answer
540 views

Is this grammar ambiguous?

I have the grammar: $\qquad \begin{align} S &\to S = P \mid S \neq P \mid P \\ P &\to NUM \end{align}$ This grammar suffers from left recursion. To eliminate left recursion, I got: $\...
7
votes
1answer
1k views

reduce reduce and shift reduce error in LALR grammar

I have to write a grammar for Pascal, and there is just one thing that is causing problems. Lets say we have operators (sorted by priority from low to high): Postfix ...
4
votes
1answer
457 views

From the LR(1) parsing table, can we deduce that it is also an LALR and SLR table?

There is this question I read somewhere but could not answer myself. Assume I have an LR(1) Parsing table. Is there any way that just by looking at it and its items, can I deduce that it is also a ...
13
votes
3answers
3k views

Why is using a lexer/parser on binary data so wrong?

I often work with lexer/parsers, as opposed to a parser combinator and see people who never took a class in parsing, ask about parsing binary data. Typically the data is not only binary but also ...
8
votes
3answers
5k views

Deriving the regular expression for C-style /**/ comments

I'm working on a parser for a C-style language, and for that parser I need the regular expression that matches C-style /**/ comments. Now, I've found this expression on the web: ...
3
votes
3answers
1k views

Understanding $\text{handle}$ in parsing problem

Originally https://math.stackexchange.com/questions/22614/help-understand-texthandle-in-parsing-problem but unaswered there The BNF is defined as followed: ...
20
votes
3answers
995 views

Parsing arbitrary context-free grammars, mostly short snippets

I want to parse user-defined domain specific languages. These languages are typically close to mathematical notations (I am not parsing a natural language). Users define their DSL in a BNF notation, ...
23
votes
1answer
357 views

Is there any nongeneral CFG parsing algorithm that recognises EPAL?

EPAL, the language of even palindromes, is defined as the language generated by the following unambiguous context-free grammar: $S \rightarrow a a$ $S \rightarrow b b$ $S \rightarrow a S a$ $S \...
70
votes
1answer
13k views

Language theoretic comparison of LL and LR grammars

People often say that LR(k) parsers are more powerful than LL(k) parsers. These statements are vague most of the time; in particular, should we compare the classes for a fixed $k$ or the union over ...

1
5 6 7 8
9