Questions tagged [parsers]

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

2
votes
1answer
94 views

What was Robert Floyd's algorithm for inserting brackets?

In page 71 of Mathematics for Computer Science (page 77 in the pdf) it says that "The Turing award (the “Nobel Prize” of computer science) was ultimately bestowed on Robert Floyd, for, among other ...
1
vote
1answer
147 views

How does SpaCy make its dependency tree?

I discovered that SpaCy had the ability to make dependency trees. For instance given a question “To whom did the Virgin Mary allegedly appear in 1858 in Lourdes France?” We can create its dependency ...
1
vote
1answer
184 views

What is handle in bottom up LR parsing?

I was taking course on compilers by Alex Aiken. You can find the slide discussing handles on this page. On the page of the slide, the instructor defines handle as follows: Assume a rightmost ...
1
vote
1answer
93 views

Why I can't parse factorial? [closed]

Given that I have a simplified Bison BNF grammar: ...
2
votes
1answer
22 views

Marginalise edge weights on graph

I have a directed acyclic graph with a score on each edge. The score of a path is defined to be the sum of the scores on the edges along this path. The probability of a path is the score of such a ...
0
votes
1answer
52 views

Can you automatically generate a parser for a type using type theory some how?

Was wondering since all the types are spelled out constructively, and the constructions can all be reflected symbolically on a computer, if you can automatically parse expressions in a type?
6
votes
1answer
69 views

Are there any context-free languages that are not known to be in $\mathrm{DTIME}(O(n))$?

The problem of determining, given a string $x$ and a context-free grammar $G$, whether $x \in L(G)$ is conjectured to take more than linear time in the length of $x$. Currently the best known ...
1
vote
0answers
306 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
42 views

Removing conflicts of LR(1) parsing tables

...
0
votes
1answer
38 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
33 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
59 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
42 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
24 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
129 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
272 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
27 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
104 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
164 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
55 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
34 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
31 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
137 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
47 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
95 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 ...
0
votes
1answer
46 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 ...
1
vote
3answers
1k 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
77 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 ...
0
votes
0answers
238 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
165 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 ...
2
votes
1answer
65 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
515 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
40 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
291 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
339 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
213 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 ...
2
votes
1answer
2k 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
62 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 of ...
0
votes
2answers
40 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
546 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?
0
votes
0answers
77 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
360 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
26 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
248 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 ? ...
1
vote
0answers
114 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
119 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
78 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
1k 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 ...
13
votes
3answers
1k 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
146 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 ...