compiler-principle

Introduction

compiler-principle

Home
1-Introduction
1-Introduction
- 1
- 1.1-Language-Processors.md
  1.1-Language-Processors.md
  - Introduction
- 1.2-The-Structure-of-a-Compiler.md
  1.2-The-Structure-of-a-Compiler.md
  - Introduction
- 1.5-Applications-of-Compiler-Technology.md
  1.5-Applications-of-Compiler-Technology.md
  - Introduction
- 1.6-Programming-Language-Basics.md
  1.6-Programming-Language-Basics.md
  - Introduction
2-A-Simple-Syntax-Directed-Translator
2-A-Simple-Syntax-Directed-Translator
- 2
- 2.1-Introduction
  2.1-Introduction
  - Introduction
- 2.2-Syntax-Definition
  2.2-Syntax-Definition
  - Introduction
- 2.3-Syntax-Directed-Translation
  2.3-Syntax-Directed-Translation
  - Introduction
- 2.4-Parsing
  2.4-Parsing
  - Introduction
- 2.7-Symbol-Tables
  2.7-Symbol-Tables
  - 2.7-Symbol-Tables
  - Symbol-table
3-Lexical-Analysis
3-Lexical-Analysis
- 3
- 3.1-The-Role-of-the-Lexical-Analyzer
  3.1-The-Role-of-the-Lexical-Analyzer
  - Introduction
- 3.4-Recognition-of-Tokens
  3.4-Recognition-of-Tokens
  - Introduction
- 3.6-Finite-Automata
  3.6-Finite-Automata
  - Introduction
- 3.7-From-Regular-Expressions-to-Automata
  3.7-From-Regular-Expressions-to-Automata
  - Introduction
4-Syntax-Analysis
4-Syntax-Analysis
- 4
- 4.2-Context-Free-Grammars
  4.2-Context-Free-Grammars
  - Introduction
- 4.4-Top-Down-Parsing
  4.4-Top-Down-Parsing
  - Introduction
- 4.3-Writing-a-Grammar
  4.3-Writing-a-Grammar
  - Introduction
- 4.5-Bottom-Up-Parsing
  4.5-Bottom-Up-Parsing
  - Introduction
- 4.6-Introduction-to-LR-Parsing-Simple-LR
  4.6-Introduction-to-LR-Parsing-Simple-LR
  - Introduction
- 4.7-More-Powerful-LR-Parsers
  4.7-More-Powerful-LR-Parsers
  - Introduction
5-Syntax-Directed-Translation
5-Syntax-Directed-Translation
6-Intermediate-Code-Generation
6-Intermediate-Code-Generation
- 6
- 6.3-Types-and-Declarations
  6.3-Types-and-Declarations
  - Introduction
7-Run-Time-Environments
7-Run-Time-Environments
9-Machine-Independent-Optimizations
9-Machine-Independent-Optimizations
- 9
Guide
Guide
- Introduction
- Parse-tree&syntax-tree
  Parse-tree&syntax-tree
  - Introduction
  - Parse-tree
    Parse-tree
    
    Introduction
  - Abstract-syntax-tree
    Abstract-syntax-tree
    
    Introduction
  - Abstract-syntax-tree-VS-parse-tree
    Abstract-syntax-tree-VS-parse-tree
    
    Introduction
  - Parse-tree-to-AST
    Parse-tree-to-AST
    
    Introduction
- Parsing-algorithm
  Parsing-algorithm
  - Introduction
  - Top-down
    Top-down
    
    Introduction
    
    Recursive-descent-parser
    Recursive-descent-parser
    
    Introduction
    
    LL-parser
    LL-parser
    
    Introduction
    
    andrewbegel-LL(1)-Parsing
    andrewbegel-LL(1)-Parsing
    
    Introduction
  - Bottom-up
    Bottom-up
    
    Introduction
    
    LR-parser
    LR-parser
    
    Introduction
    
    CYK-algorithm
    CYK-algorithm
    
    Introduction Introduction
    Table of contents
    
    wikipedia CYK algorithm
  - LL-VS-LR-Recursive-descent-Parser
    LL-VS-LR-Recursive-descent-Parser
    
    Introduction
  - Others
    Others
    
    Chart-parser
    
    Earley-parser
- Expression-tree
  Expression-tree
  - Introduction
  - Prefix-Infix-Postfix
    Prefix-Infix-Postfix
    
    Introduction
    
    Infix-notation
    Infix-notation
    
    Introduction
    
    Polish-prefix-notation
    Polish-prefix-notation
    
    Introduction
    
    Reverse-Polish-postfix-notation
    Reverse-Polish-postfix-notation
    
    Introduction
    
    Infix-to-Postfix
    Infix-to-Postfix
    
    Introduction
    
    Shunting-yard-algorithm
    Shunting-yard-algorithm
    
    Introduction
    
    Postfix-to-Prefix
    Postfix-to-Prefix
    
    Introduction
    
    geeksforgeeks-Postfix-to-Prefix-Conversion
    geeksforgeeks-Postfix-to-Prefix-Conversion
    
    Introduction
    
    Prefix-to-Infix
    Prefix-to-Infix
    
    Introduction
    
    geeksforgeeks-Prefix-to-Infix-Conversion
    geeksforgeeks-Prefix-to-Infix-Conversion
    
    Introduction
  - Build-evaluate-expression-tree
    Build-evaluate-expression-tree
    
    Introduction
  - geeksforgeeks-Expression-Tree
    geeksforgeeks-Expression-Tree
    
    Introduction
    
    Expression-Tree
    Expression-Tree
    
    Introduction
    
    Building-Expression-tree-from-Prefix-Expression
    Building-Expression-tree-from-Prefix-Expression
    
    Introduction
    
    Evaluation-of-Expression-Tree
    Evaluation-of-Expression-Tree
    
    Introduction
    
    Program-to-convert-Infix-notation-to-Expression-Tree
    Program-to-convert-Infix-notation-to-Expression-Tree
    
    Introduction
    
    Convert-ternary-expression-to-Binary-Tree
    Convert-ternary-expression-to-Binary-Tree
    
    Introduction
  - LeetCode
    LeetCode
    
    Introduction
    
    LeetCode-150-逆波兰表达式求值
    LeetCode-150-逆波兰表达式求值
    
    Introduction
  - Mathematical-Expression-Parsing
    Mathematical-Expression-Parsing
    
    Introduction
    
    Operator-precedence-parser
    Operator-precedence-parser
    
    Introduction
- Name-binding
  Name-binding
  - Introduction
- Semantic-analysis
  Semantic-analysis
  - Introduction
  - Formal-semantic
    Formal-semantic
    
    Introduction
- Program-transformation
  Program-transformation
  - Introduction
  - DMS-Software-Reengineering-Toolkit
    DMS-Software-Reengineering-Toolkit
    
    Introduction
Optimization
Optimization
- Introduction
- Basic-block
  Basic-block
  - Introduction
- Static-single-assignment-form
  Static-single-assignment-form
  - Introduction
- Control-flow-analysis
  Control-flow-analysis
  - Introduction
  - Control-flow&&program-counter
    Control-flow&&program-counter
    
    Introduction
  - Control-flow-graph
    Control-flow-graph
    
    Introduction
- Data-flow-analysis
  Data-flow-analysis
  - Introduction
- Inline
  Inline
  - Introduction
Tools
Tools
- Parser-generator
  Parser-generator
  - Introduction
  - Lex&yacc
    Lex&yacc
    
    Introduction
Implementation
Implementation
- Introduction
- Architecture
  Architecture
  - Introduction

CYK algorithm

wikipedia CYK algorithm

In computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars, named after its inventors, John Cocke, Daniel Younger and Tadao Kasami. It employs bottom-up parsing and dynamic programming.