We’re rewarding the question askers & reputations are being recalculated! Read more.

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
224 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
66 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
585 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
41 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
395 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
370 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
252 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
3k 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
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
605 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
97 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
416 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
279 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 ? ...
2
votes
1answer
154 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
134 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
82 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
166 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
220 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
963 views
3
votes
0answers
185 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
365 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
1k 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
170 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 ...
3
votes
1answer
226 views

If a grammar is SLR(1) then are the LALR and SLR tables the same?

I think they are because, SLR and LALR have same number of states and, since there are no conflicts in SLR table this means all the SLR information is needed and correctly used for parsing, so all ...
1
vote
1answer
238 views

Choosing a production with $\lambda$ in Context-Free Grammars

Given the context-free grammar \begin{align*} & S \rightarrow AA \\ & A \rightarrow xA \\ & A \rightarrow B \\ & B \rightarrow yB \\ & B \rightarrow \lambda \end{align*} What is ...
4
votes
1answer
479 views

How to find unambiguous grammar for palindromes

I am trying to figure out how to make an unambiguous grammar for palindromes over the alphabet {a, b}. I have the following, but it is ambiguous and causes conflicts in yacc. ...
0
votes
0answers
51 views

Is Kalman filter used in automata (besides cellular automata) and parsing grammars?

I am new to Kalman filter and parsers. I understand that it's suitable for prediction/estimation on the go, when you have something to measure (not only the model), and when changes always occur in ...
9
votes
2answers
757 views

Is there a different resolution of the “dangling else” problem other than “match closest”?

The following context-free grammar presents a "dangling else" type ambiguity (imagine that $a$ stands for if expr then and $b$ stands for ...
0
votes
0answers
1k views

Difference between LR parsing and Shift-Reduce parsing?

I'm learning natural language processing and I can't understand the difference between Shift-Reduce parser and LR parser. As I've understood from Wikipedia, shift-reduce is just a name of a class of ...
3
votes
2answers
2k views

Bottom-Up Evaluation of Inherited Attributes

I came across $2$ translation schemes of Syntax Directed Translation (SDT) in compilers which are as follows : Using a top-down translation scheme, we can implement any $L$-attributed definition ...
0
votes
0answers
221 views

Is this depth-first top-down parsing algorithm a recursive descent top-down parsing algorithm?

In Thomas Sudkamp's book, Machine and Languages, there is a depth-first top-down parsing algorithm (please see the algorithm here). My main question is: 1) Is this algorithm a (backtracking) ...
0
votes
2answers
509 views

Is the given grammar LL(2)?

http://dickgrune.com/Books/PTAPG_1st_Edition/BookBody.pdf The book by Grune and Jacobs presents an example of a grammar that is $LL(K + 1)$ but not $LL(K)$ The example is $S -> a^kb/a^ka$ The ...
3
votes
1answer
591 views

Eliminate left recursion from grammar

Consider the following grammar: $$ A\to Ba|Aa|c \\ B\to Bb|Ab|d $$ How do I convert this grammar to be LL(1) by eliminating direct and indirect left recursion? I have tried applying the ...
0
votes
1answer
5k views

LL(1) parsing table construction

i have the following CFG E -> ABC A-> a|Cb|epsilon B-> c|xA|epsilon C-> y|z and the First of the Non-Terminal : ...
2
votes
4answers
492 views

How to prove that Ambiguity is still present in Resolved Production of Dangling Else Problem?

$\textbf{stmt} \to$ $ \textbf{if} $expr$ \textbf{then}$ stmt $\mid $ $\textbf{if}$ expr $ \textbf{then}$ stmt$ \textbf{else}$ stmt $\mid \textbf{...
4
votes
1answer
672 views

Bottom-Up Parser With Leftmost Derivation

I'm reading the book Parsing Techniques by Dick Grune et al. and in section 3.1.3 "Linearization of the Parse Tree" they introduce the notion of linearization: [...] a parser can produce a list of ...
1
vote
1answer
264 views

boolean expression syntax checking

i am trying to formulate an algorithm for syntax checking for simple boolean expression like (var1 = 10) or (var2 > 100). evaluation part seems to be easy as i will convert infix to postfix and ...
0
votes
0answers
97 views

Is grammar S→aaab | aab in LL(2) but not SLL(2)?

I'm trying to figure out how to create grammars which are LL(k) and not SLL(i). Is this grammar LL(2) and not SLL(2)? $S \to aaab \mid aab$ Where S is a starting symbol. I think it is not SLL: ...
1
vote
0answers
61 views

Is it possible to transform this grammar into LL(1)?

This is the original grammar: S -> ABe A -> ab | a | ϵ B -> b I did try left factoring and this is what I got: ...
2
votes
3answers
487 views

Simple question about grammar derivations

I'm learning the basics of grammars and compilers for a comparative programming languages class, but having a bit of trouble with one aspect of grammar derivation. Here is an example of a grammar ...
3
votes
0answers
100 views

Unambiguous context-free language that can't be parsed in linear time by backtracking recursive descent?

Is there a context-free language that can be expressed with an unambiguous grammar but can't be expressed with a grammar that would result in linear-time backtracking recursive descent parsing? The ...
2
votes
1answer
2k views

Shunting Yard Algorithm extension and AST generation

Let me introduce you to my current project (that obviously yields the problem I face hence I post here). I am writing a so-called "compiler" for a simplistic language. I have already built a VM ...
0
votes
1answer
44 views

Can I mix LL and LR parsing?

I want to go RD parsing with Shunting Yard for expression (for the sake of easier operator precedences and less left-recusion), is that considered no-good because nobody did that before?
6
votes
2answers
297 views

any hope for a universal automatic parser?

Say you are a program, and you are given some source code but you don't know in what language, it can be C++/Java/Python/Lisp/... all you know is that it is highly structured and LR(1) parse-able, and ...
4
votes
1answer
365 views

Parsing CFLs (simulating PDA vs CYK algorithm)

We can simulate the PDA and parse the language with the following operations (vaguely): Read the input symbol and top of stack - $O(1)$ Check all the transition rules (must check all for non-...