Exploration on the board. Learning questions:
Father of modern linguistics (Professor emeritus MIT)
Type | Name | Additional restrictions |
---|---|---|
0 | Phrase structure grammar | No restrictions on form of production rules |
1 | Context-sensitive grammar | Left-hand side shorter than right-hand side for all production rules |
2 | Context-free grammar | Left-hand side of production rule is only a variable (non-terminal) |
3 | Regular grammar | Right-hand side of production rule is either a terminal or a terminal plus a variable |
Membership problem:
Given a set of data over \(\Sigma\) does it belong to \(L(G)\) ?
Type | Membership problem decidable | Complexity |
---|---|---|
0 | No | Undecidable |
1 | Yes | exponential complexity (NP-hard) |
2 | Yes | \(O(n^3)\) |
3 | Yes | \(O(n)\) (linear complexity) |
Turing Award (1977)
For profound, influential, and lasting contributions to the design of practical high-level programming systems, notably through his work on FORTRAN, and for seminal publication of formal procedures for the specification of programming languages.
Turing Award (2005)
For fundamental contributions to programming language design and the definition of Algol 60, to compiler design, and to the art and practice of computer programming.
Meta syntax (Meta language) for definition of context free grammars
twelve = "1", "2";
non-zero-number = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
digit = "0" | non-zero-number ;
natural-number = non-zero-number, { Digit } ;
integer = "0" | [ "-" ], natural-number ;
Usage | Notation |
---|---|
definition | = |
concatenation | , |
termination | ; |
alternation | | |
optional | [ … ] |
repetition | { … } |
grouping | ( … ) |
terminal string | " … " or ‘…’ |
A parser is a computer program that
Parser generator written in JavaScript