【コンパイル原理】LR(0)構文解析器を実現する
66287 ワード
実験の目的
1.文法分析の基本機能と原理に対する認識を強固にする.2.文法解析テーブルの自動生成により文法解析テーブルの認識を深める.3.文法解析における異常と誤りを理解し、処理する.
じっけんようきゅう
1.文法分析プログラムの全体的な枠組みを把握し、それを実現する.2.プログラミング構造の文法分析表に基づいて、SLR(1)分析を実現する.3.クラスの高度な言語の基本文(関数の定義、変数の説明、値の割り当て、ループ、分岐など)を構文解析できます.4.一種類の文の文法に対してその文法分析表の生成プログラムを与える(異なる文法分析方法に対応して異なる分析表を生成する).コード:
1.文法分析の基本機能と原理に対する認識を強固にする.2.文法解析テーブルの自動生成により文法解析テーブルの認識を深める.3.文法解析における異常と誤りを理解し、処理する.
じっけんようきゅう
1.文法分析プログラムの全体的な枠組みを把握し、それを実現する.2.プログラミング構造の文法分析表に基づいて、SLR(1)分析を実現する.3.クラスの高度な言語の基本文(関数の定義、変数の説明、値の割り当て、ループ、分岐など)を構文解析できます.4.一種類の文の文法に対してその文法分析表の生成プログラムを与える(異なる文法分析方法に対応して異なる分析表を生成する).コード:
// 'use static';
/*jshint esversion: 6 */
var fs = require('fs');
var write = fs.writeFileSync;
const FILE_PATH = "output.txt";
var data = fs.readFileSync(FILE_PATH).toString().trim().split('\r
').join('');
// var input = fs.readFileSync('input.txt').toString().trim();
var arr = data.split('
');
var clousure = []; //
var endIcon = ['a', 'b', '+', '=', '#']; //
var nonEndIcon = ['S', 'B', 'T', 'A']; //
var actionMap = new Array(endIcon.length);
var gotoMap = new Array(nonEndIcon.length);
var dfaMap = [];
// var grammer = ['SBB','BaB','Bb']; //
var grammer = ['ST=A', 'AB+B', 'BaB','Bb'];
function initClousure() {
/*
grammer:
item: ，
posOfDot:
*/
// let data = fs.readFileSync('data.txt').toString().trim().split('\r
');
let data = grammer;
clousure.push({
grammer:[{item: 's.S',posOfDot: 1}] //
});
clousure.push({
grammer:[{item: 'sS.', posOfDot: 2}]
});
for(let item of data) {
data[data.indexOf(item)] = item.replace(';', '');
item = item.replace(';', '');
for(let i=2;i<=item.length;i++) {
var t = {
grammer:[{item: item.slice(0, i) + '.' + item.slice(i),posOfDot: i}]
};
clousure.push(t);
}
}
for(let j=0,len=clousure.length;j<len;j++) {
let items = clousure[j];
let lastNumOfItem = items.grammer.length;
while(true) {
let item = items.grammer[items.grammer.length-1];
if(item.item.length === parseInt(item.posOfDot) + 1) {
break;
}
let char = item.item[item.posOfDot+1];
for(let i=0;i<data.length;i++) {
if(char === data[i][0]) {
let str = data[i][0] + '.';
let isExist = false;
for(let k=1;;k++) {
if(data[i].length === k) break;
str += data[i][k];
}
for(let k=0;k<items.grammer.length;k++) {
if(str === items.grammer[k].item) {
isExist = true;
break;
}
}
if(isExist) continue;
clousure[j].grammer.push({item: str, posOfDot: 1});
}
}
if(lastNumOfItem === items.grammer.length) break;
lastNumOfItem = items.grammer.length;
}
}
for(let i=0;i<clousure.length;i++) {
actionMap[i] = [];
for(let j=0;j<endIcon.length;j++) {
actionMap[i].push('err');
}
gotoMap[i] = [];
for(let j=0;j<nonEndIcon.length;j++) {
gotoMap[i].push('err');
}
}
// for(let i=0;i
// gotoMap[i] = [];
// for(let j=0;j
// gotoMap[i].push('err');
// }
// }
}
// dfa
function initDFA() {
for(let i=0;i<clousure.length;i++) {
let items = clousure[i].grammer;
for(let g=0;g<items.length;g++) {
let item = items[g];
let str = item.item;
if(item.item.length - 1 === parseInt(item.posOfDot)) continue;
let symbol = item.item[item.posOfDot + 1];
str = str.slice(0, item.posOfDot) + symbol + '.' + str.slice(item.posOfDot + 2);
for(let j=0;j<clousure.length;j++) {
let t = clousure[j];
for(let k of t.grammer) {
if(k.item == str) dfaMap.push({x: i,y:j,symbol});
}
}
}
}
}
// action goto
function initChart() {
actionMap[1][endIcon.indexOf('#')] = 'acc';
for(let i=0;i<clousure.length;i++) {
let item = clousure[i].grammer;
if(item.length === 1 && item[0].item.length === 1 + item[0].item.indexOf('.')) {
let str = item[0].item;
str = str.slice(0, str.indexOf('.'));
for(let j=0;j<grammer.length;j++) {
if(str === grammer[j]) {
for(let k=0;k<actionMap[i].length;k++) {
actionMap[i][k] = 'R' + (j+1);
}
}
}
}
}
for(let item of dfaMap) {
if(endIcon.indexOf(item.symbol) !== -1) actionMap[item.x][endIcon.indexOf(item.symbol)] = item.y;
else actionMap[item.x][nonEndIcon.indexOf(item.symbol)] = item.y;
}
for(let item of dfaMap) {
if(nonEndIcon.indexOf(item.symbol) !== -1) gotoMap[item.x][nonEndIcon.indexOf(item.symbol)] = item.y;
}
}
function analyze() {
let input = "T=A#";
let stack = "";
let status = [0];
while(true) {
stack += input[0];
let char = input[0];
input = input.slice(1);
if(actionMap[status[status.length-1]][0][0] === 'R') {
let t = parseInt(actionMap[status[status.length-1]][0].slice(1));
let str = grammer[t-1].slice(1);
stack = stack.slice(0, stack.indexOf(str));
input = grammer[t-1][0] + input;
status.pop();
} else if(endIcon.indexOf(char) === -1) {
if(nonEndIcon.indexOf(char) === -1) {
console.log('error1');
return;
}
if(gotoMap[status[status.length-1]][nonEndIcon.indexOf(char)] !== "err") {
status.push(parseInt(gotoMap[status[status.length-1]][nonEndIcon.indexOf(char)]));
while(true) {
try {
if(actionMap[status[status.length-1]][0].indexOf('R') !== -1) {
console.log(" "+actionMap[status[status.length-1]][0]+' ');
let t = parseInt(actionMap[status[status.length-1]][0].slice(1));
let str = grammer[t-1].slice(1);
stack = stack.slice(0, stack.indexOf(str));
input = grammer[t-1][0] + input;
for(let item of str) {
status.pop();
}
} else {
break;
}
} catch(e) {
break;
}
}
} else {
console.log('error2');
return;
}
} else if(actionMap[status[status.length-1]][endIcon.indexOf(char)] === "err") {
console.log('error3');
return;
} else if(actionMap[status[status.length-1]][endIcon.indexOf(char)] === "acc") {
console.log('success');
return;
} else {
if(typeof actionMap[status[status.length-1]][endIcon.indexOf(char)] === 'number') {
status.push(parseInt(actionMap[status[status.length-1]][endIcon.indexOf(char)]));
while(true) {
try {
if(actionMap[status[status.length-1]][0].indexOf('R') !== -1) {
console.log(" "+actionMap[status[status.length-1]][0]+' ');
let t = parseInt(actionMap[status[status.length-1]][0].slice(1));
let str = grammer[t-1].slice(1);
stack = stack.slice(0, stack.indexOf(str));
input = grammer[t-1][0] + input;
for(let item of str) {
status.pop();
}
}
} catch(e) {
break;
}
}
}
else {
let t = parseInt(actionMap[status[status.length-1]][endIcon.indexOf(char)].slice(1));
let str = grammer[t-1].slice(1);
console.log(" "+'r'+t+' ');
stack = stack.slice(0, stack.indexOf(str));
input = grammer[t-1][0] + input;
for(let item of str) {
status.pop();
}
}
}
}
}
function init() {
}
initClousure();
initDFA();
initChart();
analyze();