Questions tagged [parsing]

Parsing is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar.

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

Parsing a nested inference rule syntax

Consider this expression. $$\dfrac{\dfrac{\dfrac{\dfrac{}{\textsf{zero nat}}}{\textsf{succ(zero) nat}}}{\textsf{succ(succ(zero)) nat}}}{\textsf{succ(succ(succ(zero))) nat}}$$ I see several ...
0
votes
0answers
17 views

How to evaluate this type of arithmetic syntax tree in general?

I have a syntax tree, like this: Tree I can evaluate any syntax tree easily when there are no terms, with a similar code (I wrote a simpler pseudo code): ...
1
vote
1answer
62 views

An explicit algorithm to test whether a string of symbols is or is not well-formed in this language.

Consider the set of five symbols, $\{ (, ), p, ', *\}$. A variable is defined as $p$ followed by zero or more $'$s. A wff is inductively defined as follows: $1$. Every variable is a wff. $2$. If $x$ ...
0
votes
1answer
27 views

Unique parsing means?

After searching this site for the key words "unique parsing" "parsing" and "unique parsing lemma," and finding nothing really applicable to me (or as far as I could tell),...
0
votes
1answer
31 views

Is every sentential form also a right-sentential form?

Ullman's Introduction to Automata, Languages and Computing (1979) says 10.6 LR(0) GRAMMARS ... A right-sentential form is a sentential form that can be derived by a rightmost derivation. Is every ...
0
votes
0answers
12 views

How to characterize the set of grammars which recursive descent parsers can apply to?

How would you characterize the set of grammars which recursive descent parsers can apply to: no left recursion (both immediate and not) left factored no cycle no epsilon rule ... Predicative ...
0
votes
0answers
20 views

Are there subset/superset relations between the languages which can be parsed by these different kinds of parsers?

I have been confused by the different types of parsers listed in https://en.wikipedia.org/wiki/Parsing#Types_of_parsers and https://en.wikipedia.org/wiki/Template:Parsers Are there some top-down and ...
1
vote
0answers
30 views

Is a CFL parser counted as an automaton, and even a PDA?

Is a CFL parser counted as an automaton? Even more, is a CFL parser counted as a PDA? I found that a CFL parser is defined directly based on a CFG, while the concepts of CFG and PDA are defined ...
0
votes
1answer
26 views

Correctness properties, judgments and rules [closed]

Definition: sD means $s$ is a digit, i.e. $s$ is one of $0,1,\dots,9$. k Nat means $k\in\bf N$. Proposition: If sD <-> k Nat then sD and k Nat. I don't really understand what I have to prove. ...
1
vote
1answer
19 views

Proving a Formal Grammar Parses a String.

In summary, I am interested to know (at a high level) what a proof would look like, and what I would need to do in developing a grammar, to "prove" that the grammar matches some patterns I have in ...
4
votes
0answers
114 views

Can first-order logic be recognized by a pushdown automaton?

I have the belief that first-order logic cannot be recognized by a pushdown automaton because the automaton will have no way to keep track of the variables that are currently in scope. More precisely, ...
3
votes
1answer
1k views

Is First Order Logic Syntax Context Free?

If I were to build a first order logic parser could I do it using a context free parser generator (like bison)? I found some articles where First Order Logic Syntax is described with EBNF notation, ...
0
votes
1answer
47 views

This is a ll(1) of logic propositions?

I have this is grammar : F = F and F F = F or F F = F => F F = F <=> F F = not F F = (F) D = a but this grammar has a ambiguity , i'm Stripped a ...
2
votes
2answers
83 views

Interpreting “pairwise”

I have the following exercise. Can four lines in space (not necessarily passing through the same point) be pairwise perpendicular? Does it mean (given 4 lines $a$, $b$, $c$, and $d$): $a\perp b$; ...
1
vote
1answer
117 views

I am confused about how epsilon works in parsing tables (or my book is wrong)?

So I'm reading my lecture notes and something really confuses me: Shouldn't the [Y,+] entry produce an error as there is no possible way you can get the string '+' from Y? Why then does it say it ...
0
votes
1answer
555 views

Evaluating an arithmetic abstract syntax tree [closed]

This might be very simplistic for this forum (apologies, if so). How does one evaluate the tree below. I am not looking for a solution, just assistance in how to evaluate it: I assume I start at the ...
1
vote
1answer
251 views

Which of the following string have two or more parse trees?

Consider the following ambiguous grammar: $S→A|BC$ $A→aAC|B$ $C→bCc|c$ $B→aBb|\in$ Which of the following string have two or more parse trees? $aaabbbbbcc$ $aaabb$ $aabb$ None of these My ...
0
votes
1answer
76 views

Create a formula for order of parenthesis

I am stumped at creating a formula (for a coded math problem evaluator) that finds what is within the parenthesis. It gets tricky when you have () within ...
0
votes
1answer
126 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 ...
1
vote
0answers
20 views

Relationships between $\operatorname{LL}(k)$, $\operatorname{LR}(k)$ language sets

I'm trying to establish (through constructing a Hasse diagram) the subset relationship between the classes of languages that can be parsed by $\operatorname{LL}(k)$ and $\operatorname{LR}(k)$ parsers. ...
4
votes
0answers
64 views

How to read an expression that is ambiguous?

(1) How should I parenthesize $\log n \log \log n$? Also: (2) What general rule/rationale is used to do this parenthesization? To elaborate; I see why $\log\log n$ is unambiguous, but $\log n \log .....
2
votes
0answers
90 views

What is the notation for a sub-expression?

For set theory, we have notation to denote subsets, e.g.: $$S \subset X$$ When working with expressions (arithmetic, Boolean, etc.), is there a notation to denote expression $S$ is a valid sub-...
2
votes
3answers
1k views

Parenthesize expressions.

Can someone tell me how to add parenthesis to this expression $a + b \cdot c \cdot d + e$. where $a,b,c,d,e$ are algebraic variables, where addition and multiplication is as usual there. :-) ...
0
votes
1answer
632 views

Backus-Naur Form with automata

Parsers & compilers usually utilize deterministic finite automata to parse input. It's very easy to implement a generic DFA tool, that simulates any DFA table for example to validate input. ...
0
votes
3answers
88 views

grouping non-zero entries in a matrix according to a rule

I have a matrix say, $a = \left[\matrix{ 0 & 1 & 0& 0& 0& 1& 0\\ 0& 0 &0 &0 &0 &1& 1\\ 1& 0 &...
3
votes
1answer
2k views

Eliminating Epsilon Production for Left Recursion Elimination

Im following the algorithm for left recursion elimination from a grammar.It says remove the epsilon production if there is any I have the following grammer ...
2
votes
1answer
4k views

How to prove CYK algorithm has $O(n^3)$ running time

I have a final coming up in few days, and the professor mentioned the CYK algorithm. I want to be prepared for the final. I'm trying to find out how to prove the algorithm has worst case running time ...