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
54 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
2k 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
82 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
290 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
247 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
67 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
604 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
399 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
378 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
255 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
63 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
619 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
101 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
421 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
308 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
156 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
135 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
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 ...
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
170 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
221 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
973 views
3
votes
0answers
202 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
386 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
173 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
231 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
246 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
487 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
779 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
3k 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
223 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
519 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
598 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
500 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
695 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
267 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
98 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
64 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
496 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 ...