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
0 answers
14 views

What is the Parse tree for example 2.6 from Aho's Compiler Dragon Book? [closed]

I am very sorry to screen readers for the image but I want parse trees for 9 + 5 * 2 and 9 * 5 + 2. They have a grammar: ...
user avatar
1 vote
0 answers
17 views

Relation between left derivations, right derivations and number of parse trees?

I saw this question on a test-prep site Given a CFG and a string, what is the relation between the number of leftmost derivations, the number of rightmost derivations and the number of parse trees? ...
user avatar
1 vote
1 answer
39 views

How is the lookahead set computed for the Earley algorithm?

I read the dissertation [1] and the paper [2], but I'm not sure how to compute $H_{k}$. $H_{k}$ is defined as: $$H_{k}(\gamma) = \{ \alpha | \alpha \text{ is terminal,} |\alpha| = k \text{ and } \...
user avatar
0 votes
0 answers
51 views

Why is the LR(1) automaton deterministic?

Let $G = (V, \Sigma, P, S)$ be an LR(1) grammar. We can define a non deterministic $\lambda$-automaton[1] as follows. First of all we extend the grammar with an additional symbol $S'$ which will be ...
user avatar
2 votes
2 answers
115 views

LALR(1) grammar for simple math parser

I am trying to write a simple parser for a small calculator project, that should be able to parse e.g. the following inputs: ...
user avatar
  • 23
1 vote
2 answers
261 views

Proving the grammar S → SS+ | SS∗ | a is unambiguous

Consider the context-free grammar G = ({a, +, ∗}, {S}, {S → SS+ | SS∗ | a}, {S}) and consider the string aa+a* generated by this grammar. Is this grammar unambiguous? I have browsed the Internet and I ...
user avatar
  • 13
0 votes
1 answer
24 views

Lexical analysis on a series of tokens given regexes

I am to parse through a series of strings with a given token list. I was wondering if my lexical analysis is correct. ...
user avatar
  • 1
0 votes
0 answers
29 views

How to prove a number of LR(0) states?

I have this grammar $G_n, n\ge 2$: $$\begin{align}S&\to A_iB_i, 1\le i \le n\\ A_i&\to a_jA_i\mid a_j, 1\le i\land j\le n\land j\ne i\\ \end{align} $$ How can I prove that this grammar has ...
user avatar
  • 137
0 votes
0 answers
8 views

Text macros(replacements) based on pre-defined rules

I'm writing a web app that requires a component that let's the user input a piece of text thats automatically formatted based on something the client calls "macros". These macros have a very ...
user avatar
0 votes
2 answers
37 views

How to detect if a CFG can cause the parser ends up looping forever?

For example, the following grammar will never stop deriving a complete sentence: S -> A b A -> a A Some other CFGs can derive a complete sentence, but it ...
user avatar
  • 101
0 votes
1 answer
16 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\,|\...
user avatar
  • 163
0 votes
1 answer
68 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$. ...
user avatar
1 vote
1 answer
76 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 ...
user avatar
1 vote
0 answers
26 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 ...
user avatar
0 votes
0 answers
41 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 "...
user avatar
  • 9,179
2 votes
1 answer
50 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)), .... ...
user avatar
  • 9,179
2 votes
1 answer
52 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 ...
user avatar
  • 19
1 vote
0 answers
31 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: ...
user avatar
0 votes
0 answers
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: ...
user avatar
1 vote
1 answer
64 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 ...
user avatar
0 votes
0 answers
20 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 ...
user avatar
1 vote
0 answers
34 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 "?") ...
user avatar
0 votes
1 answer
29 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 ...
user avatar
1 vote
1 answer
56 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...
user avatar
0 votes
1 answer
65 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 ...
user avatar
  • 103
1 vote
0 answers
63 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 ...
user avatar
0 votes
1 answer
68 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 ...
user avatar
  • 147
1 vote
1 answer
132 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 ...
user avatar
1 vote
0 answers
29 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 ...
user avatar
1 vote
2 answers
108 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 ...
user avatar
0 votes
0 answers
47 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: ...
user avatar
0 votes
1 answer
83 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, ...
user avatar
1 vote
1 answer
89 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 ...
user avatar
  • 111
0 votes
1 answer
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. ...
user avatar
  • 1,873
1 vote
1 answer
54 views

Can given grammar be parsed using recursive descent?

I have this Grammar below: ...
user avatar
  • 131
1 vote
0 answers
14 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 ...
user avatar
1 vote
1 answer
43 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 ...
user avatar
  • 125
0 votes
1 answer
115 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 ...
user avatar
0 votes
2 answers
72 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 ...
user avatar
  • 13
0 votes
1 answer
83 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 ...
user avatar
  • 155
2 votes
2 answers
81 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 \...
user avatar
1 vote
1 answer
58 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 ...
user avatar
0 votes
1 answer
43 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 ...
user avatar
0 votes
1 answer
52 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 ...
user avatar
1 vote
1 answer
58 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 ...
user avatar
0 votes
1 answer
20 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 ...
user avatar
1 vote
0 answers
48 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 ...
user avatar
2 votes
0 answers
24 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 ...
user avatar
  • 121
0 votes
1 answer
49 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 ...
user avatar
2 votes
0 answers
29 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 <...
user avatar

1
2 3 4 5
9