Date of Award

1997

Publication Type

Master Thesis

Degree Name

M.Sc.

Department

Computer Science

Keywords

Computer Science.

Supervisor

Frost, R.

Rights

info:eu-repo/semantics/openAccess

Abstract

The efficiency of parsers can be improved by adding bookkeeping features that eliminate unnecessary backtracking. In this thesis we investigate a technique called memoization. A memoized parser computes its result based on previously computed results that have been stored in a memo-table. A parser is a program that determines the syntactic structure of an input sequence of symbols in some language. It may produce some kind of abstract syntax tree as output. We consider the simplest type of parsers--language recognizers that can be thought of as programs determining only if the input sequence belongs to a given language. We show that memoized recognizers constructed for an arbitrary grammar have O(n$\sp3$) time complexity where n is the length of the input to be processed. The space required to store the memo table is (at most) O(n$\sp3$). In purely functional programming languages that support updateable in-place variables the space requirements could be reduced to O(n$\sp2$). Monads, which are abstract structures from Category Theory, have proven useful for addressing many computational problems in purely functional programming. (Abstract shortened by UMI.) Paper copy at Leddy Library: Theses & Major Papers - Basement, West Bldg. / Call Number: Thesis1996 .S99. Source: Masters Abstracts International, Volume: 37-02, page: 0638. Adviser: Richard A. Frost. Thesis (M.Sc.)--University of Windsor (Canada), 1997.

Download

Share

COinS