Stack Overflow
Stack Overflow

Questions tagged [chomsky-hierarchy]

The Chomsky hierarchy is a containment hierarchy of classes of formal grammars.

Within the field of computer science, specifically in the area of formal languages, the Chomsky hierarchy (occasionally referred to as Chomsky-Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars. This hierarchy of grammars was described by Noam Chomsky in 1956.1 It is also named after Marcel-Paul Schützenberger, who played a crucial role in the development of the theory of formal languages. The Chomsky Hierarchy, in essence, allows the possibility for the understanding and use of a computer science model which enables a programmer to accomplish meaningful linguistic goals systematically. wikipedia

40 questions
36
votes
5 answers

Is there a standard C++ grammar?

Does the standard specify the official C++ grammar? I searched, but did not find it anywhere. Also, I wish to read a bit about C++ grammar in detail, like which category of grammars it falls in, etc. Any links pointing me in the right direction…
Lazer
  • 90,700
  • 113
  • 281
  • 364
19
votes
3 answers

The difference between Chomsky type 3 and Chomsky type 2 grammar

I'm having trouble articulating the difference between Chomsky type 2 (context free languages) and Chomsky type 3 (Regular languages). Can someone out there give me an answer in plain English? I'm having trouble understanding the whole hierarchy…
Jay Jenkins
  • 413
  • 1
  • 5
  • 15
18
votes
3 answers

chomsky hierarchy and programming languages

I'm trying to learn some aspects of the Chomsky Hierarchy which are related to programming languages, and i still have to read the Dragon Book. I've read that most programming languages can be parsed as a context free grammar (CFG). In term of…
dader
  • 1,304
  • 1
  • 12
  • 31
16
votes
2 answers

Chomsky Language Types

I'm trying to understand the four different Chomsky language types but the definitions that I have found don't really mean anything to me. I know type 0 is free grammar, type 1 is context sensitive, type 2 is context free whilst type 3 is regular.…
John
  • 1,566
  • 6
  • 17
  • 28
10
votes
2 answers

How should Chomsky's Hierarchy and Turing Machines influence language design?

I'm currently studying for a discrete mathematics test in which we are learning Chomsky's hierarchy and the type of automatas that recognize each level of the hierarchy. I'm being taught that most computer languages fall within "level 2 and 1" of…
andandandand
  • 21,946
  • 60
  • 170
  • 271
8
votes
1 answer

Is Rust's lexical grammar regular, context-free or context-sensitive?

The lexical grammar of most programming languages is fairly non-expressive in order to quickly lex it. I'm not sure what category Rust's lexical grammar belongs to. Most of it seems regular, probably with the exception of raw string literals: let s…
Lukas Kalbertodt
  • 79,749
  • 26
  • 255
  • 305
7
votes
4 answers

What kind of language is SQL?

Is SQL a context free language or some other type of language?
Abhinav Arya
  • 225
  • 3
  • 9
6
votes
2 answers

Is Rust's syntactical grammar context-free or context-sensitive?

The syntactical grammar of hardly any programming language is regular, as they allow arbitrarily deeply nested parenthesis. Rust does, too: let x = ((((())))); But is Rust's syntactical grammar at least context-free? If not, what element makes the…
Lukas Kalbertodt
  • 79,749
  • 26
  • 255
  • 305
6
votes
5 answers

Recursive languages vs context-sensitive languages

In Chomsky's hierarchy, the set of recursive languages is not defined. I know that recursive languages are a subset of recursively enumerable languages and that all recursive languages are decidable. What I'm curious about is how recursive languages…
Martin Konecny
  • 57,827
  • 19
  • 139
  • 159
5
votes
1 answer

Example of Non-Linear, UnAmbiguous and Non-Deterministic CFL?

In the Chomsky classification of formal languages, I need some examples of Non-Linear, Unambiguous and also Non-Deterministic Context-Free-Language(N-CFL)? Linear Language: For which Linear grammar is possible( ⊆ CFG) e.g. L1 = {anbn | n ≥ 0 }…
Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
4
votes
2 answers

Chomsky Hierarchy and LL(*) parsers

I want to parse a programming language. I read a lot about formal languages and the Chomsky hierarchy and ANTLR. But I could not find information on how to relate the languages ANTLR v3 as an LL(*) recursive descent parser accepts to the chomsky…
meelow
  • 861
  • 1
  • 7
  • 10
2
votes
1 answer

Regexp parse type-3 grammar

Reading Chomsky hierarchy ... ... I know regexp can't parse type-2 grammars (context-free grammars), and also type-1 and type-0. Can regular expressions parse/catch ALL type-3 grammars (regular grammars)?
Alberto
  • 2,881
  • 7
  • 35
  • 66
2
votes
0 answers

Chomsky Hierarchy and Robot Framework

I am writing a thesis about Robot Framework. I would like include a part about Chomsky Hierarchy, and describe in which hierarchy, does it belong to. As far as i can understand it, most programming languages can be described by CFG (Context Free…
Samo Branisa
  • 53
  • 1
  • 5
2
votes
1 answer

Chomsky hierarchy - examples with real languages

I'm trying to understand the four levels of the Chomsky hierarchy by using some real languages as models. He thought that all the natural languages can be generated through a Context-free Grammar, but Schieber contradicted this theory proving that…
Babbara
  • 448
  • 1
  • 6
  • 21
2
votes
2 answers

Is a Chomsky type 1 parser generator possible?

Looking at the Chomsky hierarchy of grammars I find that for Type 2 grammars (context free grammars) very good tools exist to aid in creating software to read these from text into a usable data structure in memory. In my experience Antlr4 is one of…
Niels Basjes
  • 10,424
  • 9
  • 50
  • 66
1
2 3