Experiment Objectives

• Understand the mechanics of recursive descent parsing and its potential for backtracking.
• Implement a recursive descent parser for context-free grammars.
• Evaluate the generalizability and limitations of recursive descent parsers.

Preparation

1. Review the section on top-down parsing techniques.
2. Familiarize yourself with a chosen development environment such as VC++.

Experiment Content

Select one of the following grammars to implement:

1. Arithmetic Expression Grammar

E → TE'
E' → +TE' | ε
T → FT'
T' → *FT' | ε
F → (E) | i

Implement a recursive descent parser that validates arithmetic expressions like j+k*m or j*k+m. Input should be tokenized by a lexical analyzer (e.g., i+i*i, i*i+i). Output should indicate whether the expression syntax is valid.

2. Pascal Identifier Type Grammar (Optional)

type   → simple | id | array [ simple ] of type
simple → integer | char | num dotdot num

Implement a parser to validate type declarations such as array [num dotdot num] of integer.

Requirements

1. Develop and test the program. Analyze how easily the parser can be adapted for other grammars and evaluate its strengths and weaknesses.
2. Prepare an experiment report covering: experiment name, objectvies, content, results, and analysis.

Implementation Examples

Example 1: Arithmetic Expression Parser

#include <iostream>
#include <string>
#include <vector>

using namespace std;

enum class TokenType {
    Identifier,
    Plus,
    Star,
    LParen,
    RParen,
    End
};

struct Token {
    TokenType type;
    string text;
    Token(TokenType t, string s) : type(t), text(move(s)) {}
};

class Lexer {
public:
    Lexer(const string& input) : input_(input), pos_(0) {}

    vector<Token> tokenize() {
        vector<Token> tokens;
        while (pos_ < input_.size()) {
            char ch = input_[pos_];
            if (isspace(ch)) {
                ++pos_;
            } else if (ch == 'i') {
                tokens.emplace_back(TokenType::Identifier, "i");
                ++pos_;
            } else if (ch == '+') {
                tokens.emplace_back(TokenType::Plus, "+");
                ++pos_;
            } else if (ch == '*') {
                tokens.emplace_back(TokenType::Star, "*");
                ++pos_;
            } else if (ch == '(') {
                tokens.emplace_back(TokenType::LParen, "(");
                ++pos_;
            } else if (ch == ')') {
                tokens.emplace_back(TokenType::RParen, ")");
                ++pos_;
            } else {
                cerr << "Unknown character: " << ch << endl;
                ++pos_;
            }
        }
        tokens.emplace_back(TokenType::End, "#");
        return tokens;
    }

private:
    string input_;
    size_t pos_;
};

class Parser {
public:
    explicit Parser(const vector<Token>& tokens) : tokens_(tokens), pos_(0) {}

    bool parse() {
        return E() && match(TokenType::End);
    }

private:
    const vector<Token>& tokens_;
    size_t pos_;

    const Token& current() const {
        return tokens_[pos_];
    }

    bool match(TokenType expected) {
        if (current().type == expected) {
            ++pos_;
            return true;
        }
        return false;
    }

    bool E() {
        return T() && EPrime();
    }

    bool EPrime() {
        if (current().type == TokenType::Plus) {
            match(TokenType::Plus);
            return T() && EPrime();
        }
        return true;
    }

    bool T() {
        return F() && TPrime();
    }

    bool TPrime() {
        if (current().type == TokenType::Star) {
            match(TokenType::Star);
            return F() && TPrime();
        }
        return true;
    }

    bool F() {
        if (match(TokenType::Identifier)) {
            return true;
        } else if (match(TokenType::LParen)) {
            if (E() && match(TokenType::RParen)) {
                return true;
            } else {
                return false;
            }
        }
        return false;
    }
};

int main() {
    vector<string> tests = {
        "i+i*i",
        "i*i+i",
        "i+*i",
        "(i+i)*i",
        "((i))",
        "i+"
    };

    for (const auto& expr : tests) {
        Lexer lexer(expr);
        auto tokens = lexer.tokenize();

        Parser parser(tokens);
        cout << "Testing expression: " << expr << endl;
        if (parser.parse()) {
            cout << "✅ Valid syntax" << endl;
        } else {
            cout << "❌ Invalid syntax" << endl;
        }
        cout << "-----------------------" << endl;
    }

    return 0;
}

Example 2: Pascal Type Grammar Parser

#include <iostream>
#include <string>
#include <vector>

using namespace std;

enum class TokenType {
    Identifier,
    Number,
    Integer,
    Char,
    Array,
    Of,
    LBracket,
    RBracket,
    DotDot,
    End
};

struct Token {
    TokenType type;
    string text;
    Token(TokenType t, string s) : type(t), text(move(s)) {}
};

class Lexer {
public:
    explicit Lexer(const string& input) : input_(input), pos_(0) {}

    vector<Token> tokenize() {
        vector<Token> tokens;
        while (pos_ < input_.size()) {
            char ch = input_[pos_];
            if (isspace(ch)) {
                ++pos_;
            } else if (isalpha(ch)) {
                string ident;
                while (isalnum(input_[pos_])) ident += input_[pos_++];
                if (ident == "array") tokens.emplace_back(TokenType::Array, ident);
                else if (ident == "of") tokens.emplace_back(TokenType::Of, ident);
                else if (ident == "integer") tokens.emplace_back(TokenType::Integer, ident);
                else if (ident == "char") tokens.emplace_back(TokenType::Char, ident);
                else tokens.emplace_back(TokenType::Identifier, ident);
            } else if (isdigit(ch)) {
                string num;
                while (isdigit(input_[pos_])) num += input_[pos_++];
                tokens.emplace_back(TokenType::Number, num);
            } else if (ch == '.' && peek() == '.') {
                tokens.emplace_back(TokenType::DotDot, "..");
                pos_ += 2;
            } else if (ch == '[') {
                tokens.emplace_back(TokenType::LBracket, "[");
                ++pos_;
            } else if (ch == ']') {
                tokens.emplace_back(TokenType::RBracket, "]");
                ++pos_;
            } else {
                cerr << "Invalid character: " << ch << endl;
                ++pos_;
            }
        }
        tokens.emplace_back(TokenType::End, "#");
        return tokens;
    }

private:
    string input_;
    size_t pos_;

    char peek() const {
        return (pos_ + 1 < input_.size()) ? input_[pos_ + 1] : '\0';
    }
};

class Parser {
public:
    explicit Parser(const vector<Token>& tokens) : tokens_(tokens), pos_(0) {}

    bool parse() {
        return parseType() && match(TokenType::End);
    }

private:
    const vector<Token>& tokens_;
    size_t pos_;

    const Token& current() const {
        return tokens_[pos_];
    }

    bool match(TokenType expected) {
        if (current().type == expected) {
            ++pos_;
            return true;
        }
        return false;
    }

    bool parseType() {
        if (match(TokenType::Integer) || match(TokenType::Char) || match(TokenType::Identifier)) {
            return true;
        }
        if (match(TokenType::Array)) {
            if (!match(TokenType::LBracket)) return false;
            if (!parseSimple()) return false;
            if (!match(TokenType::RBracket)) return false;
            if (!match(TokenType::Of)) return false;
            return parseType();
        }
        return false;
    }

    bool parseSimple() {
        if (match(TokenType::Integer) || match(TokenType::Char)) {
            return true;
        }
        if (match(TokenType::Number)) {
            if (!match(TokenType::DotDot)) return false;
            if (!match(TokenType::Number)) return false;
            return true;
        }
        return false;
    }
};

int main() {
    vector<string> tests = {
        "array[3..5] of integer",
        "array [ integer ] of char",
        "char",
        "3..5",
        "array[3..x] of integer"
    };

    for (const auto& input : tests) {
        Lexer lexer(input);
        auto tokens = lexer.tokenize();

        Parser parser(tokens);

        cout << "Testing: " << input << endl;
        if (parser.parse()) {
            cout << "✅ Valid syntax\n";
        } else {
            cout << "❌ Invalid syntax\n";
        }
        cout << "------------------------\n";
    }

    return 0;
}