context-free-grammar - 将上下文无关语言转换为下推自动机的程序？

Question

我在网上找不到任何小程序或程序来将上下文无关语言转换为下推自动机......任何帮助将不胜感激。

Answer 1

用手很容易做到。PDA 具有开始状态 s 和最终状态 f，这是它仅有的两个状态。进行转换 ((s, empty, empty),(f, S))，其中 S 是 CFG 的开始符号。对于每个规则 X -> Y，其中 X 是非终结符，Y 是可能为空的终结符和非终结符字符串，进行转换 ((f, empty, X),(f,Y))。最后，对于每个终结符号 a，添加规则 ((f, a, a),(f, empty))。

这样做是通过将开始符号压入堆栈开始。然后它将在堆栈顶部找到的任何非终结符替换为其产生式规则的右侧，并匹配并弹出堆栈顶部的任何终结符。

Answer 2

请查看代码：https ://github.com/P-Raj/AutomataPlus 。它不仅包含用于将 CFG 转换为 PDA 的代码，还包含用于其他类似任务的代码。

Answer 3

试试这个软：https ://github.com/navrkald/regularConvertor 。您可以逐步抛出将 CFG 转换为 PDA 的整个算法。它使用 Qt 用 C++ 编写，在部分版本中，您已经为 Windows 构建了自可执行二进制文件。

Answer 4

#include<bits/stdc++.h> 
using namespace std;

 int main()
 {

int n; 
cout<<"Enter the no of Production Rules of CFG"; 

cin>>n; 
char s1; 
string s2; 
vector<pair<char,string>> v;

 cout<<"Please enter the Production rules of CFG \n";

  for(int i=0;i<n;i++)
    { cin>>s1>>s2;

      v.push_back(make_pair(s1,s2));}

cout<<"The Corresponding Production Rules For PDA are:-"<<endl; 



 cout<<"Rules For Non-Terminal Symbols are:- \n";

for(int i=0;i<n;i++){
 int flag=0; 
 cout<<"dl(q,null," <<v[i].first<<") --> ";

 string check=v[i].second;
 int si=check.size();

string ans="";
for(int i=0;i<si;i++){ char ch=check[i];


    if(ch == '|')
        { cout<<"dl(q,"<<ans<<") |";

              ans="";}

  else{ ans+=ch;}

  }


if(flag!=1) cout<<"dl(q,"<<ans<<")"<<endl;

}

cout<<"dl(q,0,0)--> dl(q,null)"<<endl; 
cout<<"dl(q,1,1) --> dl(q,null)"<<endl;
}