Write a program to check whether a grammar is operator precedent.
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;
// Data structure to represent a production rule
struct Production
{
string left;
string right;
};
// Function declarations
unordered_set<string> collectTerminals(const vector<Production> &productions);
bool checkOverlappingSymbols(const unordered_set<string> &terminals, const unordered_set<string> &operators);
bool checkAdjacentNonTerminals(const vector<Production> &productions);
// Function to check if the grammar is operator precedence
bool isOperatorPrecedence(const vector<Production> &productions)
{
unordered_set<string> terminals = collectTerminals(productions);
unordered_set<string> operators;
// Collect operators
for (const Production &production : productions)
{
for (char symbol : production.right)
{
string symbolStr(1, symbol);
if (!isalpha(symbol) || !islower(symbol))
{
operators.insert(symbolStr);
}
}
}
// Check for overlapping symbols between terminals and operators
if (!checkOverlappingSymbols(terminals, operators))
{
return false;
}
// Check if the grammar is operator precedence
return !checkAdjacentNonTerminals(productions);
}
// Function to collect terminals from the production rules
unordered_set<string> collectTerminals(const vector<Production> &productions)
{
unordered_set<string> terminals;
for (const Production &production : productions)
{
terminals.insert(production.left);
for (char symbol : production.right)
{
if (isalpha(symbol) && islower(symbol))
{
terminals.insert(string(1, symbol));
}
}
}
return terminals;
}
// Function to check for overlapping symbols between terminals and operators
bool checkOverlappingSymbols(const unordered_set<string> &terminals, const unordered_set<string> &operators)
{
for (const string &terminal : terminals)
{
if (operators.count(terminal))
{
return false;
}
}
return true;
}
// Function to check for adjacent non-terminals in the production rules
bool checkAdjacentNonTerminals(const vector<Production> &productions)
{
for (const Production &production : productions)
{
string right = production.right;
if (right.length() >= 2 && isalpha(right[0]) && isalpha(right[1]) && isupper(right[1]))
{
return true; // Invalid adjacent non-terminals
}
}
return false;
}
int main()
{
// Define the grammar with production rules
vector<Production> productions = {
{"E", "E+T"},
{"E", "T"},
{"T", "T*F"},
{"T", "F"},
{"F", "(E)"},
{"F", "id"}};
// Check if the grammar is operator precedence
if (isOperatorPrecedence(productions))
{
cout << "The grammar is operator precedence." << endl;
}
else
{
cout << "The grammar is not operator precedence." << endl;
}
return 0;
}
Comments
Post a Comment