C# Predictive Parsing Algorithm Implementation with First and Follow Sets

This C# code implements a predictive parsing algorithm for a given context-free grammar. The algorithm leverages the First and Follow sets of each non-terminal symbol to build a parsing table, which is then used to parse an input string.

GetSelect() Method

The GetSelect() method is responsible for constructing the parsing table. It iterates through each non-terminal symbol in the grammar and its production rules. For each production rule, it calculates the Select set, which is the set of all terminal symbols that can follow the non-terminal symbol in that production rule. Here's how it works:

1. Terminal Symbol: If the first symbol in the production rule is a terminal symbol, it's added directly to the Select set.
2. Non-Terminal Symbol: If the first symbol is a non-terminal symbol:
   • The First set of that symbol is added to the Select set.
   • If the First set contains the empty string ('#'), the Follow set of the non-terminal symbol is also added to the Select set.

Analyze() Method

The analyze() method parses an input string using the parsing table created by GetSelect(). It simulates the parsing process using a stack-based approach. Here's a breakdown:

1. Initialization: If the grammar's start symbol is not already on the analysis stack, it's pushed onto it.
2. Parsing Loop: The algorithm iterates until either the analysis stack or the input stack becomes empty.
3. Symbol Comparison: The top elements of the analysis stack and input stack are compared.
   • Match: If they match, both symbols are popped from their respective stacks.
   • Mismatch: If they don't match:
     • Terminal on Top: If the analysis stack's top is a terminal symbol, an error is reported.
     • Non-Terminal on Top: The parsing table is consulted for a matching production rule based on the top stack symbol and input symbol.
       • Production Rule Found: The non-terminal is popped from the stack, and the right-hand side of the production rule is pushed onto the stack in reverse order.
       • No Production Rule: An error is reported.
4. Result: The process continues until either the entire input string is parsed successfully or an error occurs.

Data Structures

• resultAnalyse, resultInput, and resultParse lists store intermediate parsing results, helping to generate a report on the parsing's success or failure.

Example Usage

This code demonstrates how to use the predictive parsing algorithm to parse a simple arithmetic expression.

// Example Grammar
Dictionary<string, List<string>> production = new Dictionary<string, List<string>>
{
    {'E', new List<string> {'TA'}},
    {'A', new List<string> {'+TA', '#'}},
    {'T', new List<string> {'FB'}},
    {'B', new List<string> {'*FB', '#'}},
    {'F', new List<string> {'(E)', 'id'}} 
};

// Example Input String
string input = 'id+id*id'; 

// ... (rest of the code to initialize and call the parsing algorithm)

This implementation provides a practical example of how to build a predictive parser in C#, a valuable tool in compiler design and language processing.