Questions tagged [parsers]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
14 views

Computing Earley Parsing Steps

I am trying to understand Earley parsing algorithm using an example. The grammar I use produces all the palindromes over $\Sigma=\{a,b,c\}$: \begin{align*} Z & \to S\\ S & \to a\,|\,b\,|\,c\,|\...
0
votes
1answer
30 views

Reduce-reduce conflict in SLR vs LALR

I was wondering if I could say any of the following is true. Given a grammar $G$, If the LALR parser has reduce-reduce conflict for $G$, then the SLR parser also has reduce-reduce conflict for $G$. ...
1
vote
1answer
52 views

Why can't a LR(0) parser have GOTO and Reduce Items in the same canonical set?

I am talking in reference to this question from this compiler test. I think it is actually true that a GOTO and REDUCE can't be present in the same set, but am having a hard time coming up with an ...
1
vote
0answers
16 views

How does one parse a string into an AST (Abstract Syntax Tree) directly instead of to a CST (Concrete Syntax Tree)?

I wanted to parse strings to AST data structures instead of CSTs - which introduce a lot of intermediate nodes like terminal that might not be needed. I am not sure if one first creates a CST and then ...
0
votes
0answers
18 views

How to prove that this "priority" strategy (in ANTLR4) solves the "dangling-else" ambiguity?

As shown in this post @ stackoverflow, ANTLR4 seems able to resolve the "dangling-else" ambiguity @ wiki in the following "if-then-else" grammar by prioritizing the "...
2
votes
1answer
35 views

How does LALR(1) parser behave compared to LR(1) paser?

In Section 4.7.4 of the book "Compilers: Principles, Techniques, and Tools" (2nd Edition), it reads: "The revised parser (LALR(1)) behaves essentially like the original (LR(1)), .... ...
2
votes
1answer
30 views

Convert a dfa to rule for a asterisk case

Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is ...
1
vote
0answers
27 views

Parse algebraic expression into a list of operations

Given algebraic expression in a string, I want to split it into a list of operations for building a parallel binary tree. For example, I'm trying to convert expression such as: ...
0
votes
0answers
8 views

An RDP Rule consumed a token and the other rule can't parse the sentence

I am constructing an LL(1) parser (Recursive Descent Parser) and I need to parse the sentence a = 3, I have two procedures to match that rule: ...
1
vote
1answer
47 views

How to write a non-ambiguous grammar for the syntax of lambda calculus?

I tried to write a non-ambiguous grammar for lambda calculus, but it does not really work. The recursive-descent parser is easy to write though. I googled but all results I collected so far are ...
0
votes
0answers
13 views

Tips on making a grammar LL(1)?

So I currently am given the following grammar, and I have to make it LL(1). To do this, I need to remove ambiguities, eliminate left recursion, and left factor if necessary. But looking at this, it's ...
1
vote
0answers
27 views

Should a lexer (tokenizer) handle unknown operators?

I have a list of supported operators, my question is whether the lexer should just yield the token for the operator or raise a syntax error in case that particular operator (let's say "?") ...
0
votes
1answer
28 views

LALR lookahead is wrong, why?

I am studying LALR(1) parser and I have this question: Consider the following Grammar S - > V = E E - > F | E+F F - > V | int | (E) V - > id Construct the LALR(1) parsing table for this ...
1
vote
1answer
45 views

set theory with RegEx on fen strings (or another parser)

how can you find if a regex call is a subset of another regex call on an predictable set of data I have a string (chess Forsyth–Edwards Notation (FEN) string...
0
votes
1answer
34 views

Convert regex pattern to LL1 parser

Background: I'm trying to solve this leetcode problem: regular-expression-matching. My approach is to implement a LL(1) parser generator, might be overkilling for this problem but it's just a brain ...
1
vote
0answers
29 views

Handling infinite loop in implementation Pushdown Automaton (PDA)

I've got a basic implementation of a Pushdown Automaton which recursively checks the rules of a grammar in CNF to find whether a given input string is accepted or not, and it can also count the number ...
0
votes
1answer
32 views

Why does bottom-up parsing of right-recursive grammars require unbounded O(n) stack space?

I keep reading that while bottom-up parsing of a left-recursive grammar can be done in constant O(1) stack space, for a right-recursive grammar, we have to push the entire input stream onto the stack ...
1
vote
1answer
98 views

Hierarchy of parser grammars vs Chomsky hierarchy of grammars and the comparsion of the language acceptance power of each parser grammar

While reading the text Modern Compiler Implementation in C by Andrew Appel I came across the hierarchy of grammar given below. The above diagram is very helpful in understanding the correlation among ...
1
vote
0answers
25 views

Condition of LL(3) grammer

To find out whether a grammar G is LL(1) or not, we test this condition among other conditions, "If whenever A -> alpha | beta are two distinct productions ...
1
vote
2answers
101 views

Are parse trees always produced?

When my instructor taught compiler construction he explained all the phases of compiler and their working nicely. But when I read online here, at last line it is written that Parse trees are not ...
0
votes
0answers
46 views

Why the grammar is not (LL1)?

Why the grammar is not (LL1)? (e is the epsilon) $$S \to a A \mid b B \mid a C c $$ $$A \to a A \mid a a A \mid e $$ $$B \to c C \mid D \mid e $$ CHOICE 1: The grammar is Left-Recursive (LR) CHOICE 2: ...
0
votes
1answer
71 views

How are lexical tokens produced

I am studying Compiler Design. The instructor told us that when a program is given to lexical analyzer it find all tokens then a symbol table is created and it is updated at every phase accordingly, ...
1
vote
1answer
74 views

More efficient way to parse array into binary search tree

Let's assume I have array which I need to parse into binary tree ...
0
votes
1answer
20 views

How would you specify a grammar that can parse letters separated by single underscores?

In JavaScript, let's say, it is easy to build a string intermixed with single underscores by just joining the string parts. ...
0
votes
0answers
28 views

What's the point in a symbol table or AST when all the information is available in the parse tree?

This is a question I haven't worked out the answer to yet probably because I haven't done any hands on middle end compiler design. I feel like the explanation of the true purpose of an AST were ...
1
vote
1answer
47 views

Can given grammar be parsed using recursive descent?

I have this Grammar below: ...
1
vote
0answers
12 views

How do bottom up parser evaluate things that need an inherited attribute?

I learned that Bottom up parsers use only synthesized attributes to evaluate semantics. Which makes sense considering that it would be very hard to evaluate an inherited attribute in bottom up ...
1
vote
1answer
33 views

Parse forest from an ambiguous grammar

Parser-generators like nearleyjs can return a parse forest instead of a parse tree. Since not all input may result in a parse forest (eg, the input may exercise ...
0
votes
1answer
80 views

Grammar for $\{a^n b^n c^m d^m \mid n \geq 1, m \geq 0\}$

I'm trying to understand how the construction of simple grammars works. In my textbook, there's the following example I am supposed to find a grammar for: Let $L_1= \{a^n b^n c^m d^m \mid n \geq 1, m ...
0
votes
2answers
58 views

A state machine that is either DFA or NFA: is it possible?

I am studying Crafting Interpreters, and although I understand the responsibility of the Scanner (or Lexer), I still cannot understand if it is a deterministic finite automaton or non-deterministic ...
0
votes
1answer
55 views

BNF syntax for a recursive function?

I'm to write a syntax that will allow for a recursive function, i.e. f(x) = if x == 0 then x else f(x+1) Here's one attempt at creating the grammar: But I don't ...
1
vote
0answers
43 views

Generating a recursive descent parser for grammar having Kleene star

From what I have been taught, I cannot use left-recursive, nondeterministic, or ambiguous grammars in recursive descent parsers. So, here is the grammar: \begin{align} &E \to E+T \mid T \\ &T \...
1
vote
1answer
55 views

Would a parser for this left-recursive grammar require infinite input?

I am considering this left recursive language grammar production rule: Expr = Expr, "a" ; As a production rule, I believe that this can be used to ...
0
votes
0answers
23 views

Parsing HTML from HTTP vs HTTPS websites

Are there any alternative steps to receiving and then parsing the HTML of an unsecured site (HTTP) vs a secured site (HTTPS)? I am asking as I learnt that there is encryption involved in the HTTPS ...
0
votes
1answer
39 views

How is $A.in$ an inherited attributed in $2nd$ production in $(1) S \rightarrow A_1A_2\{ A_1.in := 1; A_2.in := 2 \}(2) A\rightarrow a\{print(A.in)\}$

Below is an excerpt from the Red Dragon book. $$(1) \quad S \rightarrow A_1 \quad A_2 \quad\{ A_1.in : = 1;\quad A_2.in : = 2 ;\}$$ $$(2) \quad A \rightarrow a \quad \{ print(A.in) \}$$ We find that ...
0
votes
1answer
45 views

L-attributed definitions include all syntax-directed definitions based on LL(1) grammars

I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the following claim: L-attributed definitions include all syntax-directed definitions ...
1
vote
1answer
52 views

In syntax-directed definition, terminals are assumed to have synthesized attributes only, definition doesn't provide any semantic rules for terminals?

I was going through the text Compilers: Principles,Techniques and Tools by Ullman et. al. where I came across the claim in the question by authors. Below is the definition and following it is the ...
0
votes
1answer
19 views

$\text{"The error entries in the goto table are never consulted"}$ - intuitive explanation of the above claim with respect to $LR$ parsing tables

I was going through the text : Compilers: Principles, Techniques and Tools by Ullman et. al where I came across a claim: $\text{"The error entries in the goto table are never consulted"}$ I feel ...
1
vote
0answers
41 views

Understanding the concept of "Viable Prefixes"

I was going through the text: Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the concept of viable prefix and I faced some difficultly in grasping the concept. So I ...
0
votes
0answers
279 views

In shift reduce parsing why the handle always eventually appear on top of the stack and never inside?

I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al where I came across the excerpt where the authors try to justify why stack is the best data structure of shift ...
2
votes
0answers
23 views

Generating an "approximate" grammar

This is my first time posting here, so I hope I'm on topic. I have a table of natural-language data of the form ...
0
votes
0answers
26 views

Why can't I evaluate this L-Attributed SDD with a pre-order traversal?

My powerpoints for a compiler class says "an L-Attributed SDD can be evaluated with a pre-order (root, left, right) traversal", and to be L-Attributed the nodes need to have either ...
0
votes
1answer
37 views

CYK algorithm in theory of computation

For any context free grammar, there is a parser that takes atmost n^3 time to parse a string of length n. Doubt: I marked it false in a national level exam.I think it should be any null-free context ...
2
votes
0answers
22 views

Unparsing an operator grammar in the face of ambiguity

I'm using the grammar scheme of Danielsson and Norell ("Parsing Mixfix Operators"). The short version is: user defined mixfix operators such as _+_ or <...
3
votes
1answer
60 views

How is `y λx.x y` parsed using the standard pure untyped lambda calculus conventions?

How would the following term in the pure untyped lambda calculus be parsed: y λx.x y The relevant conventions listed on https://en.wikipedia.org/wiki/...
-1
votes
1answer
39 views

Compilers: how to find first and follow sets?

I sort of know how to solve the problem but I am not sure how to do it in a systematic way. Could someone provide a step-by-step solution especially for the follow set one? Thanks!
1
vote
1answer
55 views

How to handle L-attributed SDDs with LR parsers

I've read Chapter 5, Syntax Directed Translation, of the Dragon Book but am still unable to understand the following related points: How to handle L-attributed SDDs in an LR grammar when using a tool ...
0
votes
1answer
21 views

Compilers: How to see "the number of grammars where there exists a string that has at least two different left-most derivations"?

Could someone tell why "G1 and G3 are ambiguous" and how to see whether a string has at least two different left-most derivations in general?
0
votes
0answers
21 views

I am trying to design an LL(1) Parser that accepts T = {a, b *, +, ?, E, U, (, ) }

I am trying to design an LL(1) Parser that accepts regular notation where 'E' represents epsilon, and 'U' represents "or" like ' | '. So far I made one that accepts T = { a, b, *, +, (, ), E}...
0
votes
1answer
143 views

Computing FOLLOW sets of left recursive grammar

Left recursive ambiguous expression Grammar: $E \rightarrow E+E \mid E*E \mid (E) \mid \mathbf i\mathbf d$ I tried computing FIRST and FOLLOW sets of both left recursive grammar and after ...

1
2 3 4 5
9