4.1 TOP-DOWN PARSING

INTRODUCTION

A syntax analyzer or parser is a program that performs syntax analysis. A parser obtains a string of tokens from the lexical analyzer and verifies whether or not the string is a valid construct of the source language-that is, whether or not it can be generated by the grammar for the source language. And for this, the parser either attempts to derive the string of tokens w from the start symbol S , or it attempts to reduce w to the start symbol of the grammar by tracing the derivations of w in reverse. An attempt to derive w from the grammar's start symbol S is equivalent to an attempt to construct the top-down parse tree; that is, it starts from the root node and proceeds toward the leaves . Similarly, an attempt to reduce w to the grammar's start symbol S is equivalent to an attempt to construct a bottom-up parse tree; that is, it starts with w and traces the derivations in reverse, obtaining the root S .