[go: up one dir, main page]

DeRemer, 1971 - Google Patents

Simple LR (k) grammars

DeRemer, 1971

View PDF
Document ID
16863219305575680667
Author
DeRemer F
Publication year
Publication venue
Communications of the ACM

External Links

Snippet

A class of context-free grammars, called the “Simple LR (k)” or SLR (k) grammars is defined. This class has been shown to include weak precedence and simple precedence grammars as proper subsets. How to construct parsers for the SLR (k) grammars is also shown. These …
Continue reading at dl.acm.org (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/20—Handling natural language data
    • G06F17/27—Automatic analysis, e.g. parsing
    • G06F17/2705—Parsing
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30964—Querying
    • G06F17/30979—Query processing
    • G06F17/30985—Query processing by using string matching techniques
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/20—Handling natural language data
    • G06F17/21—Text processing
    • G06F17/22—Manipulating or registering by use of codes, e.g. in sequence of text characters
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/20—Handling natural language data
    • G06F17/27—Automatic analysis, e.g. parsing
    • G06F17/2765—Recognition
    • G06F17/277—Lexical analysis, e.g. tokenisation, collocates
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/3061—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F17/30634—Querying
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/3061—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F17/30613—Indexing
    • G06F17/30619—Indexing indexing structures
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10—TECHNICAL SUBJECTS COVERED BY FORMER USPC
    • Y10S—TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y10S707/00—Data processing: database and file management or data structures
    • Y10S707/99931—Database or file accessing
    • Y10S707/99933—Query processing, i.e. searching
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme

Similar Documents

Publication Publication Date Title
DeRemer Simple LR (k) grammars
Knuth Top-down syntax analysis
Tomita An Efficient Context-Free Parsing Algorithm for Natural Languages.
Goodman Parsing algorithms and metrics
US6778949B2 (en) Method and system to analyze, transfer and generate language expressions using compiled instructions to manipulate linguistic structures
Koo et al. Automata-based constraints for language model decoding
US6944588B2 (en) Method and apparatus for factoring unambiguous finite state transducers
US6961693B2 (en) Method and apparatus for factoring ambiguous finite state transducers
Nilsson AID: An alternative implementation of DCGs
US7107205B2 (en) Method and apparatus for aligning ambiguity in finite state transducers
US6952667B2 (en) Method and apparatus for extracting infinite ambiguity when factoring finite state transducers
Huang et al. Machine translation as lexicalized parsing with hooks
US6965858B2 (en) Method and apparatus for reducing the intermediate alphabet occurring between cascaded finite state transducers
Lang The systematic construction of Early Parsers: Application to the production of an O (n^ 6) Early Parser for Tree Adjoining Grammars.
US6959273B2 (en) Method and apparatus for factoring finite state transducers with unknown symbols
US6760636B2 (en) Method and apparatus for extracting short runs of ambiguity from finite state transducers
Pugh Extending Graham-Glanville techniques for optimal code generation
Lin et al. Context-free grammar parsing by message passing
Meijer The project on extended affix grammars at Nijmegen
Carter Lattice-based word identification in CLARE
Thant Implementing Syntax analyzer For Compilation Process
Nederhof Transition-based dependency parsing as latent-variable constituent parsing
Handzhiyski et al. Tunnel Parsing with Ambiguous Grammars
Zakzok et al. Improved Upper Bounds for Determinizing NIDPDAs with Limited Nondeterminism
Hausser Discontinuous Structures in DBS and PSG