Incremental Expression Parsing for Syntax-Directed Editors

Abstract

This document describes an algorithm for incremental parsing of expressions in the context of syntax-directed editors for programming languages. Since a syntax-directed editor represents programs as trees and statements and expressions as nodes in trees, making minor modifications in an expression can be difficult. To make these changes in a typical syntax-directed editor, the user must understand the tree structure and type a number of tree-oriented construction and manipulation commands. This document describes an algorithm that allows the user to think in terms of the syntax of the expression as it is displayed on the screen (in infix notation) rather than in terms of its internal representation (which is effectively prefix), while maintaining the benefits of syntax-directed editing. The time and space complexities of the modifications for each new token are linear in the depth of the syntax tree.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 27, 1982
Accession Number
ADA122152

Entities

People

  • Elaine Kant
  • Gail E. Kaiser

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Collapse
  • Computer Programming
  • Computer Science
  • Computers
  • Environment
  • Language
  • Law
  • Personal Computers
  • Personality
  • Programming Languages
  • Sequences
  • Software Development
  • Standards
  • Template Patterns
  • Terminals
  • Trees (Data Structures)

Fields of Study

  • Computer science

Readers

  • Computer Science.
  • Geochemistry
  • Neural Network Machine Learning.

Technology Areas

  • Space