Questions tagged [parsers]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
727 views

Are LL(1) grammars a subset of LR(0) grammars?

As far as I've understood it seems that LL1 are a subset of LR0, but studying the following grammar I end up in a contraddiction. Grammar : S -> (S) | [S] | {S} | ε This is an LL1 while it seems ...
1
vote
1answer
124 views

Removing conflicts of LR(1) parsing tables

...
0
votes
1answer
43 views

What is Follow(X) when there's a rule, A -> XBCD where First(B) and First(C) contain empty, but First(D) do not

I have a question about follow sets. Suppose there's a rule, A -> XBCD B -> $\beta$ | $\epsilon$ C -> $\gamma$ | $\epsilon$ D -> $\delta$ What is Follow(X)? Is it (First(B) - $\...
2
votes
0answers
136 views

Expanding an Earley parse forest

I have a small context-free grammar, which I would like to use to turn input strings into parse trees. I need to get all possibilities in case of ambiguity (so shift-reduce is out), and there's quite ...
1
vote
1answer
109 views

How do I build a left derivation tree from an expression including right-to-left associativity?

Suppose I want to make a left derivation tree of an expression, but the expression includes operators that are right-to-left associative. Would I still expand the left-most variable first in my tree? ...
0
votes
1answer
59 views

Can we use Operator precedence parsing with this grammar?

This Grammar: A-->Bbab|aa B-->b I think we can't because basically there is no relation between terminals? like no relation between a and b! or am i missing something? and the language of this ...
-1
votes
1answer
25 views

Parsing table confusion [closed]

I've been researching the different answers I've been given to this, would somebody just be able to give me a clear answer of the difference between Shift, reduce and go-to. - In a parsing table. Of ...
3
votes
1answer
155 views

Is there a name for this tree traversal?

This came when I was looking at block scoping in compiler design. { A { B } { C {D} {E} } } For the above pseudo code, the order in which the scope ...
1
vote
0answers
492 views

Can a YACC parse an ambiguous grammar

I found a question while studying compilers :- Given a grammar E->E+E/E×E/number The above grammar is fed to a YACC with semantic rules for parsing. What will be the action of the YACC. 1) it ...
0
votes
0answers
30 views

Name for a property of grammars

Parsing s-expressions is almost trivial. This is true for both automated processes (and thus implies ease of implementation of such processes) and for a human readers of printed s-expressions. It is ...
3
votes
1answer
124 views

Why doesn't the C/C++ compilers create different tokens for different types of numbers?

Based on GeeksforGeeks and many other sites, the C/C++ compilers will create the same token for float/int etc. However if we ...
2
votes
1answer
275 views

Should we eliminate left recursion before using NPDA to simulate CFG?

I read the book "Introduction to the Theory of. Computation, Third Edition by Michael Sipser". It says: If a language is context free, then some pushdown automaton recognizes it. Let A be a ...
1
vote
0answers
83 views

Generate an AST from an indefinite grammar and logic

As said in the title, I have to generate an AST from a grammar and logic (or a"syntax" if you prefer). This grammar and syntax are both indefinite in the program, meaning that it is the user (a ...
2
votes
1answer
47 views

Formalism for unambiguous context-sensitive languages?

I know that there are some languages that are unambiguous but not context-free (this is a good fact). Is there any kind of formalism for describing unambiguous context-sensitive languages? Even better ...
0
votes
1answer
34 views

extend ECMAScript by adding new keywords and syntax

I would like to extend ECMAScript by adding new keywords and syntax to it, for example: |variableName| stipulates a special kind of variable which I would like to be able to include in a normal ...
2
votes
1answer
269 views

Conversion of ambiguous left recursive grammar to LL(1)

I have been strugling with this LL(1) transformation for far longer than expected and am getting quite desperate. We are given a grammar $ G = \left\{V_N, V_T, S, \Phi \right\}$, with the non-terminal ...
0
votes
1answer
77 views

How to define whitespace for certain rules but else ignore it

I am trying to make a programming language for the first time and wonder how it handles whitespace. I can see CFG by default seem to just ignore whitespaces, but what if I want it to use it sometimes? ...
1
vote
2answers
163 views

CFG - Left factoring in recursive nested productions

I'm attempting to convert a CFG into an LL(1) grammar for predictive parsing in a compiler. I've been able to left factor and eliminate left recursion and ambiguity for every case in the grammar, with ...
1
vote
1answer
106 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 ...
2
votes
3answers
3k 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 <...
2
votes
0answers
87 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 ...
1
vote
0answers
443 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$ ...
0
votes
1answer
470 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 ...
3
votes
1answer
78 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 ...
2
votes
1answer
1k 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 ...
1
vote
1answer
43 views

Follow set confusion about inclusion

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 ...
2
votes
1answer
639 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 ...
0
votes
1answer
576 views

LL1 parsing algorithm for strings generated by a given grammar

How to describe a $\operatorname{LL(1)}$ parsing algorithm for strings generated by a given grammar? I have to design a parser for a specific grammar. Let $G$ be the grammar described as: $$S \...
0
votes
1answer
304 views

How to build a parser for syntactic analysis of regular expressions?

Is it possible to build a parsing algorithm that build a parse tree using a top-down method that simulate a derivation process for regular expressions, like we do for type 2 languages? My guess ...
4
votes
1answer
7k views

What is a "sentential form"?

I do know what a "left-most-" and a "right-most derivation" is, but I stumble across the term "sentential form" and its specific differences "right-sentential form" as well as "left-sentential form" ...
0
votes
1answer
106 views

Compiler Question : Does the parser detect Errors in these examples or the Semantic routine?

For example, which part will detect these errors, Parser or Semantic Routine? 1) int Array[10.5] ( wrong size ) 2) int x="some string" 3) A[10.5] + 3 (not in declaration, but in the middle ...
0
votes
2answers
43 views

What does the $^*$ operator do in the theory of parsing?

I'm currently reading through Aho's "Theory of parsing, translation and compiling" on my own and I got a bit confused about the closure operator on language $L$ with alphabet $\Sigma$ ($L^*$). The ...
0
votes
0answers
840 views

Proof of every regular language has a LL(1) grammar

I tried some examples and found that LL(1) grammar always exist. I tried searching for formal proof but didn't find any. Can someone give a formal proof for the above statement?
1
vote
0answers
537 views

Convert Source Code into English Text?

Is there a way to convert, i.e., C code into English? The purpose would be to convert source code into a Text-To-Speech converter which would enable someone to "listen" to source code. EDIT: An ...
3
votes
1answer
550 views

Where does LL parser belong in the top-down parsers classification

There are four types of top-down parsers according to this answer: recursive descent backtracking recursive descent predictive table-driven with backtracking table-driven predictive. Also the author ...
3
votes
0answers
27 views

How to model grammar ambiguity

Say you have a (context-free) grammar, and you wish to mathematically model the magnitude of the ambiguity possible under this grammar, across the space of all possible** input strings. Practically, ...
2
votes
0answers
479 views

SLR vs CLR parser

In SLR we use follow set of a non terminal for determining reduce moves and in CLR we use lookaheads for the same. How does using lookaheads actually help in improving the performance of the parser ? ...
4
votes
1answer
288 views

The upper bound on a Nondeterministic Finite Automata's configurations number

In "Engineering: A Compiler" 2nd ed. by Cooper and Torczon, in 2.4.1 "Nondeterministic Finite Automata" of Chapter 2, section "Equivalence of NFAs and DFAs" discusses the upper bound of a NFA's ...
1
vote
0answers
163 views

Can the HTML5 parsing algorithm be implemented in linear time?

Can the HTML5 parsing algorithm (https://html.spec.whatwg.org/multipage/parsing.html#parsing) be implemented in $O(n)$, or at worst $O(n\mathop{log}n)$, time, even for malicious input? It seems ...
1
vote
0answers
86 views

Where is left recursion in this little CF grammar?

S → D D → E | EC E → anyId C → B | .D | B.D B → <S> | <SA> A → ,S | ,SA The tool I am using keeps complaining about left recursion in this grammar. I ...
1
vote
4answers
2k views

Eliminating cycles from a grammar

I have the following grammar: S -> Xb | Y Y -> X | a X -> S | c Here the lowercase letters are terminals. I have an algorithm to find the cycle in ...
14
votes
3answers
2k views

What would you get if you add parameters to context free grammars?

I was thinking of grammars for indendation-sensitive languages and it looks like CF grammars would do the trick if combined with parameters. As an example, consider this fragment for simplified Python ...
1
vote
0answers
229 views

Is the Java 8 Grammar still a LALR(1) grammar?

As I found out here: http://www.eclipse.org/jdt/core/howto/generate%20parser/generateParser.html , the Java Version of 2005 (might be Java 6, I'm not sure) is a LALR(1) grammar. However, I couldn't ...
0
votes
1answer
380 views

Neither Left nor Rightmost Derivations

Consider a simple grammar and its derivations. The derivations could be done in leftmost or rightmost patterns and can also be done in no particular order as the derivation order has no effect on the ...
1
vote
0answers
41 views

Determining the set of valid next terminals when generating from a CFG

I am trying to generate random sentences from a context-free grammar. During each step, the next non-terminal to be generated is determined according to some probabilistic criteria irrelevant to this ...
8
votes
2answers
1k views
3
votes
0answers
279 views

How would I build a parser generator for a context free grammar using Pushdown Automata?

I am building a parser generator, not for any project in particular, just for fun to improve my understanding of parsing, grammars, languages, etc. I am at the point where I have lexer generation ...
2
votes
1answer
847 views

Understanding context free grammars in conjunction with PDA

I have read TONS of articles about context free grammars and Pushdown Automata but I think there are things that I dont seem to understand. I am not studying computer science but I am really ...
3
votes
1answer
2k views

How to generate an LL(2) parse table?

The algorithms I've seen for building an LL(1) parse table involve calculating first and follow sets such that: ...
1
vote
0answers
210 views

Converting Ambiguous Grammar G to LL(1)

So I am in the process of learning about LL(1) grammar and converting an ambiguous one into LL(1). I know how to figure out if a grammar (G) is ambiguous, however, I am having trouble converting it to ...

1 2 3
4
5
9