Programming languages and their compilers: Preliminary notes

By John Cocke. 1969

Subfields: Program Analysis & Verification

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Program Analysis & Verification

Citations in the corpus

Grammar-Based Grounded Lexicon Learning (2022, methodology): “, the CKY algorithm [22, 45, 10]) to compose sentence meaning from lexical meaning forms, based on syntax.”
Learning Syntax from Naturally-Occurring Bracketings (2021, methodology): “The best scoring tree among all valid treesY can be found using the CKY algorithm (Cocke, 1969; Kasami, 1965; Younger, 1967).”
Learning to Compose Task-Specific Tree Structures (2017, methodology): “Unsupervised Tree-LSTM (Maillard et al., 2017) resolves this ambiguity while maintaining the soft property by introducing the concept of CYK parsing algorithm (Kasami, 1965; Younger, 1967; Cocke, 1970).”
ListOps: A Diagnostic Dataset for Latent Tree Learning (2018, methodology): “(2017) present uses a CYK-style (Cocke, 1969; Younger, 1967; Kasami, 1965) chart parser to compute a soft combination of all valid binary parse trees.”
Head-Driven Phrase Structure Grammar Parsing on Penn Treebank (2019, methodology): “As shown in Figure 4, our parsing model includes four modules: token representation, self-attention encoder, scoring module and CKY-style decoder 7 .”
A Bottom-Up DAG Structure Extraction Model for Math Word Problems (2021, methodology): “(2016) predicted the expression tree by Cocke-Younger-Kasami algorithm (Cocke 1969) and SVM.”
Latent Tree Learning with Differentiable Parsers: Shift-Reduce Parsing and Chart Parsing (2018, background): “(2017) is based on chart parsing, and effectively works like a CKY parser (Cocke, 1969; Kasami, 1965; Younger, 1967) using a grammar with a single nonterminal A with rules A → A A and A → α, where α is any terminal.”
Category-theoretic quantitative compositional distributional models of natural language semantics (2013, methodology): “any introduction to language theory, computational linguistics, or mathematical linguistics. Ecient parsing algorithms have been developed to recover the 53 CFG structure from digital text (e.g. CYK [15, 50, 89], Earley [25]), and a large number of corpora and other resources have been created to as”
Span-based Semantic Parsing for Compositional Generalization (2020, methodology): “Furthermore, as i<j log c ′ exp [ s’ ( x i : j , c ′ )] does not depend on T at all, maximizing log p ( T ) is equivalent to maximizing the tree score: This scoring function can be maximized using CKY ( Cocke, 1969; Kasami, 1965; Younger, 1967).”
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both? (2020, methodology): “This enables efficient parsing using an algorithm similar to CKY (Cocke, 1969; Kasami, 1966; Younger, 1967) that does not require binarization of the grammar.”