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

learn more… | top users | synonyms (1)

0
votes
0answers
15 views

LL(k) vs Strong LL(K)

What is the diference between LL(K) and strong LL(K) grammars definitions? LL(k): For every pair of production rules A→α and A→β the following condition holds. FIRSTk(αy) ∩ FIRSTk(βy) = ∅ ...
0
votes
0answers
12 views

Which implementation algorithms in the updated Lexers and Parsers are more advanced and efficient? [closed]

I want to write a lexer and parser based on C# language in new microsoft framework .NET Core. So I have investigation about the knowledge of implementation similar libraries. Comparison of parser ...
0
votes
2answers
39 views

Proving that a CFG generates a language [duplicate]

Is a suitable way to prove that any given CFG generates (or not) any given language to draw its total language tree? What if the tree is infinite? What would then be a better way to prove that a ...
2
votes
1answer
44 views

Does my grammar contradict LL ⊆ LR(1)?

This answer claims that $ LL \subseteq LR \left( 1 \right )$ where $LL = \bigcup_k LL(k)$. But is this true? Is this grammar a valid counterexample? $ S \rightarrow a | Aaa $, $ A \rightarrow \...
0
votes
1answer
18 views

Is there any precedence for symbols for constructing parse trees? [duplicate]

I am wondering if some symbols such as the ones in propositional logic have precedence over others in drawing parse trees. For example, the sentence: p ∧ q → r, ...
5
votes
0answers
71 views

What would a formal grammar for a binary file format look like?

Binary structures often feature length specifiers; the parser is supposed to read them and then consume the specified amount of symbols. Because of this, the grammar is context-sensitive. What would ...
0
votes
1answer
21 views

Unsure about parse tree of PCFG

I'm new to build parse trees and I'm really unsure if I'm doing this right. So I have this example Grammar (S->Sa, S->aSa, S->a) and the word I'm parsing is simply aaaa. My solution would look like ...
0
votes
0answers
21 views

In a recursive descent parser, when do the evaluation and parsing phases need to be separated?

I'm unsure of the distinction between an evaluation and parsing phase in a recursive descent parser and I'm having trouble finding information about that. What sorts of functions require or do not ...
2
votes
1answer
12 views

Why is particular token missing in LALR lookahead set?

I ran the following grammar (pulled from the dragon book) in the Java Cup Eclipse plugin: S' ::= S S ::= L = R | R L ::= * R | id R ::= L The items associated ...
1
vote
0answers
14 views

How do merged lookahead sets help LALR parse more grammars than SLR? [closed]

From what I have searched on Google so far, the only difference between LALR(1) and SLR(1) is that LALR(1) uses states with merged lookahead sets. One source says that LALR(1) won't run into shift-...
-3
votes
1answer
43 views

What's the step for build a SLR table for the following CFG? [closed]

(r1) E → E+T (r2) E → T (r3) T → T F (r4)T →F (r5) F → F∗ (r6) F → a (r7) F → b I am just doing the exercise on the workshop. I just knew how to the build the SLR state machine for this CFG. ...
1
vote
1answer
34 views

operator precendence grammar

According to this post http://stackoverflow.com/questions/28397767/computing-leading-and-trailing-sets-for-context-free-grammar while constructing operator precendence parser we have to create tabel ...
3
votes
1answer
48 views

Is the word problem of CFLs in NC?

Consider the membership problem for a context-free language. An instance of this problem can be described as pair $(G,w)$, where $G$ is a context-free grammar and $w$ is a string. Lets say I have a ...
0
votes
0answers
25 views

Left recursion elimination and LL(1) parsing table construction

As part of our homework we were asked to eliminate left recursion then constructing LL(1) parsing table of the following grammar: $E\rightarrow E-T$ $E\rightarrow T$ $T\rightarrow num$ ...
1
vote
0answers
12 views

How can we avoid mistake in LL(1) parse tree?

I'm learning about LL(1) parse tree. We need to find first and follow in order to construct a LL(1) parse tree. Each and every ...
0
votes
1answer
22 views

Lookahead in LL(k) parsing

I'm having difficulty understanding what lookahead is $\mathrm{LL}(k)$ parsing. Does $k$ lookahead mean I consume $k$ symbols at a time and then process them? Any help is appreciated.
3
votes
2answers
53 views

Meta-grammar for context-free grammars

Formal grammars like regular expressions (REs) or context-free grammars (CFGs) specify languages, i.e. sets of strings over an alphabet. Grammars themselves can be seen as languages, e.g. the set of ...
2
votes
0answers
88 views

How does this left-associative recursive descent parser work?

For personal enlightenment, I'm trying to write a recursive descent parser for lambda calculus without abstraction, i.e., just identifiers and function application. The BNF grammar that describes the ...
3
votes
1answer
95 views

Need for an augmented grammar

The question is under the concept of LR parser. Suppose the original grammar is S->AA A->aA|b Is it necessary to add an additional rule S'->S to make it as augmented grammar? In short, I want to ...
-1
votes
2answers
71 views

I'm having trouble with Parse Trees

I am doing homework and I have the following problem: Consider the grammar: ...
0
votes
1answer
31 views

Is the given grammar LALR

We are given the following grammar. S-->AS/b A-->SA/a We have to tell if its LALR or not. As we all know that LALR is only minimization of CLR, So first I constructed the CLR parsing table using ...
0
votes
1answer
49 views

Need to remove indirect left recursion from CFG

I need to remove indirect left recursion from the following CFG: remove indirect left recursion from the following CFG. $$A → Ba| b$$ $$B → Cd | e$$ $$C → Df | g$$ $$D → Df | Aa | Cg$$ In the ...
0
votes
0answers
22 views

Parsing text in two dimensions

I would like to define grammar rules which define how a token is related not only to the left and to the right (as in usual stream of characters that parses deal with), but also to the top and to the ...
0
votes
0answers
24 views

how to determine the action from the stack using the LR parsing tables?

I've been having a hard time wrapping my mind around the LR parsing table. Say I have the following table given the input action of id+id*id$ how does Stack <...
0
votes
2answers
33 views

Is the number of operators always one less than the number of values in an arithmetic Reverse Polish Notation expression with only binary operators?

Is the number of operators always one less than the number of values in an arithmetic Reverse Polish Notation expression with only binary operators? This question seems very trivial, but I don't know ...
0
votes
0answers
36 views

Can valid sub-parses be added to an earley chart after a successful parse has been recognized?

I'm implementing the Earley algorithm and am trying to build a parse forest from the output of the recognizer. However in the process of doing so I got this output from an ambiguous CFG, where a non-...
1
vote
0answers
49 views

Upper bound of automaton states for SLR parsing

How do I tell, given a specific grammar, which is the upper bound for the number of states of a LR(0) or LR(1) automaton for its SLR parsing? My guess is that generating the canonical item collection ...
1
vote
1answer
36 views

How to treat $\epsilon$ and '$' in top-down predictive parsing (predict table)?

How to treat $\epsilon$ and '\$' in top-down parser using predict table? The construction of the predict table Given a product $X \rightarrow w$, row $X$ and column $t$ -Mark $X \rightarrow w$ ...
1
vote
1answer
31 views

Indirect Left recursion

I'm solving (indirect Left Recursion) for these production rules . S is the starting symbol. S -> Aa / a eq1 A -> Sb / b. eq2 Now I can do this in two ...
1
vote
0answers
49 views

How to find conflicts in LALR parser?

I have a LR analyser and I can't find out how to know whether the grammar is or is not LALR(1). I think that I have to merge states with the same rules. So I have to merge states: $2 - 12, 3 - 13, 4 -...
3
votes
1answer
288 views

How can I check that the language of one context-free grammar is a subset of a second context-free grammar?

Could you explain me, how can I check, that the language of first context-free grammar (G1) is a subset of the language of second context-free grammar (G2). G1 and G2 are two LL(1) grammars with ...
-2
votes
1answer
55 views

Basic idea behind error recovery in recursive-descent parsers

I see that modern SW basically dominated by recursive descent parsers. These parsers try grammar production and back track to an alternative one in case of failure. Suppose BNF is ...
1
vote
1answer
43 views

How to treat ϵ-productions in table-driven predictive parsing?

Here: https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html in chapter Driver Procedure, it's shown how table-drive predictive parsing works. The predict table however can ...
0
votes
1answer
64 views

Trouble understanding how to create a grammar parse tree

I'm starting an online Computer Science class called Advanced Programming Languages, and the book asks me to create a parse tree and generate a grammar from it. Here are the exact instructions: ...
0
votes
2answers
67 views

Is the language $L=\{a^nb^n\} \cup \{aa*\}$ DCFL?

Is the language $L=\{a^nb^n\} \cup \{aa*\}$ DCFL OR CFL? The author says $L$ is CFL, but I am able to generate a Deterministic PDA for the corresponding language. I am naive in this subject and hence ...
1
vote
3answers
133 views

Does precedence matter in constructing parse trees of arithmetic expressions for postfix notation?

Table 4 in Problem Solving with Algorithms and Data Structures's chapter on Infix, Prefix and Postfix Expressions gives the following examples: ...
0
votes
1answer
19 views

In top-down parser how do you match a product $A \rightarrow a_1 | a_2 | …$, $a_i$s terminals

One procedure for table-driven top-down parsing is given here: https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html This gives for matching the input the lines: ...
4
votes
2answers
121 views

What is the point of delimiters and whitespace handling

I see that language specifies reserved words, delimiters and whitespaces in the lexer section. Are delimiters just like reserved identifiers in the punctuation space or they have additioinal function ...
0
votes
2answers
52 views

Is C → A B C | A left-factorizable?

$$C \to A B C \mid A$$ Obviously has the same FIRST(C) for the both productions. But how can this be left-factorised? Tried: $$C \to A B C'$$ $$C' \to A C \mid \varepsilon$$ The FIRST sets are ...
1
vote
1answer
87 views

Cocke-Younger-Kasami (CYK) algorithem for the word $baabb$

With the context-free grammar in Chomsky's form:$$S\to BA|AC|b\\A\to AA|AB|CC|a\\B\to AS|BB|CA\\C\to AB|SS|b$$ I need to: run the CYK (Cocke-Younger-Kasami) algorithm and decide if I can ...
0
votes
1answer
54 views

Are parser combinators equivalent to scannerless parsing?

From what I can see, parser combinators are equivalent to scannerless parsing. I do not see this stated in implementations of scannerless parsing page, nor in the parsing combinators page, neither in ...
-2
votes
1answer
63 views

Automata vs Earley parsing? [closed]

If the language is implementable as mere DFA (i.e. it's a regular language), then why would one need a parsing algorithm such as Earley. Regular languages are a subset of context-free languages, but ...
0
votes
1answer
31 views

In NLP, does the lexer have to tag the tokens before the parser?

In NLP, does the lexer have to tag the tokens before the parser? I.e. does the lexer have to classify the tokens to morphological categories before the parser? I'm thinking yes, but is this also the ...
1
vote
1answer
27 views

Duplicating the quotation marks in in the quotation-mark enclosed strings

There is such a grammar string_literal ::= " { graphic_character } " The double-quotes that you see must appear in the user program and curly braces mean "any ...
0
votes
1answer
28 views

How to detect plurals in English sentences?

I'm wondering how to detect English plurals in natural language sentences. Such as: fish computers houses ... Using Earley parsing I'm able to get to the s or no-s, but I have difficulties in ...
-2
votes
1answer
65 views

How should I show that a grammar is not LL(1) and convert grammar to LL(1)

I'm trying to find the ambiguity in this grammar so I can remove it and convert it to LL(1), however for the life of me, I can't find the ambiguity. Moreover, I think there is cycle between X and Y ...
6
votes
0answers
49 views

Is THEADS the same as FIRST?

I'm reading the paper "A Practical General Method for Constructing LR(k) Parsers" by David Pager, and it contains the following paragraph: We will first of all briefly review the LR(1) parsing and ...
1
vote
0answers
36 views

Parsing based on logical connectives and quantifiers?

What techniques exist for parsing sentences based on logical connectives and quantifiers? That is, for parsing sentences that are structured "around" logical connectives and quantifiers. E.g. [A] ...
0
votes
1answer
76 views

What exactly is the LL(k) grammar condition?

I have a bit of trouble understanding the definition of LL(k) grammars. Here it's defined as: for every pair of production rules $A\rightarrow α$ and $A \rightarrow β$ the following ...
0
votes
1answer
79 views

Construct SLR Parse table problems

Consider the augmented grammar G is: S` -> S S -> a S -> (T) T -> T,S T -> S I have tried to construct parse table. But, when I read '(' ...