A NECESSARY AND SUFFICIENT CONDITION FOR A CONTEXT-FREE GRAMMAR TO BE UNAMBIGUOUS

Abstract

A class of context-free grammers called first-character-recognition grammars (or fcr grammars) is defined. These grammars obviously satisfy the necessary and sufficient condition; consequently, they are unambiguous. It is shown to be a decidable question, whether a given grammar is an fcr grammar. Many programming languages can be described by fcr grammar. Many programming languages can be described by fcr grammars; ALGOL can be so described, except for the distinction between arithmetic and Boolean expressions.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 28, 1965
Accession Number
AD0620657

Entities

People

  • Val Schorre

Organizations

  • System Development Corporation

Tags

DTIC Thesaurus Topics

  • Character Recognition
  • Computer Programming
  • Context Free Grammars
  • Demographic Cohorts
  • Formal Languages
  • Grammars
  • Language
  • Linguistics
  • Personality
  • Production
  • Programming Languages
  • Recognition
  • Sequences
  • Terminals

Readers

  • Computer Engineering
  • Systems Analysis and Design