王鸿百学年论文

哈尔滨师范大学

学 年 论 文

题 目 算符优先函数的构造 学 生 王鸿百

指导教师 肖鑫 教授 年 级 2009级

专 业 计算机科学与技术 系 别 计算机系

学 院 计算机科学与信息工程学院

哈尔滨师范大学

2012 年 6 月

论 文 提 要

算符优先分析法是自下而上语法分析的一种，它的算法简单、直观、易于理解，所以通常作为学习其它自下而上语法分析的基础。为学好本章内容，学员应复习有关语法分析的知识，如：什么是语言、文法、句子、句型、短语、简单短语、句柄、最右推导、规范归约基本概念。

算符优先函数的构造

王鸿百

摘 要：算符优先分析法是Floyd在1963年首先提出来的，是一种古典而又实用的方法，用这种方法在分析程序语言中的各类表达式时尤为有效。不少编译程序中都使用这种方法分析表达式。算符优先分析法就是仿照算术表达式的运算过程而提出的一种自底向上的语法分析方法。其基本思想是：首先规定算符，这里是文法的终极符之间的优先关系，然后根据这种优先关系，通过比较相邻算符的优先次序来确定句型中的“句柄”，然后进行归约。算符优先分析法的关键：算符优先分析法的关键就是寻找当前句型中的最左素短语，并归约它。 关键字：小于、大于、等于、句柄、归约

一、对表达式文法G[ E’]构造算符优先关系表。

计算算符优先只针对于终结符，终结符之间的优先关系有三种，在计算优先关系之前我们先定义两个集合，对于任意两个终结符（a,b）FIRSTVT（B）={b|B=>b?或B=>Cb?},其中?表示V＊中的符号串。

LASTVT（B）={a|B=>?a或B=>?aC}

三种优先关系：（1）等于关系:可直接查看产生式的右部,对如下形式的产生式A->?ab?

A->? aBb?则有a=b成立。

（2）小于关系：求出每个非终结符B的FIRSTVT（B）， 观察如下形式的产生式A->?aB?对每一 b∈FIRSTVT(B)有a≮b成立

（3）大于关系：计算每个非终结符B的LASTVT（B），观察如下形式的产

生式A->?Bb?对每一 a∈LASTVT(B)有a≯b成立

表达式文法G[ E’]：

E’ →# E # E → E + Q | Q Q → Q - T | T T → T * F | F F → F/ M｜M M → M^ P｜P P → ( E )｜i

根据上面的规则手工构造上述文法的算符优先表如下：

+ - + ≯ ≯ - ≮ ≯ * ≮ ≮ / ≮ ≮ ^ ≮ ≮ （ ≮ ≮ ） ≯ ≯ i ≮ ≮ # ≯ ≯ * / ^ （ ） i # ≯ ≯ ≯ ≮ ≯ ≯ ≮ ≯ ≯ ≯ ≮ ≯ ≯ ≯ ≯ ≯ ≮ ≯ ≯ ≮ ≮ ≯ ≯ ≮ ≯ ≯ ≮ ≮ ≮ ≯ ≮ ≯ ≯ ≮ ≮ ≮ ≮ ≮ ≯ ≯ ≯ = ≯ ≯ ≮ ≮ ≮ ≮ ≮ ≯ ≯ ≯ ≯ ≯ = 表 1-1 package com.op.core;

/*******************************************************************************

* 简单表达式文法G[ E’]构造算符优先关系表。 * E’ →# E # * E → E + Q | Q * Q → Q - T | T * T → T * F | F * F → F / M｜M * M → M ^ P｜P * P → ( E )｜i * @author */

public class PriorityTable {

private static char table[][] = { // + * / i ( ) # ^

{ '>', '<', '<', '<', '<', '>', '>', '<' }, // + { '>', '>', '>', '<', '<', '>', '>', '<' }, // * { '>', '>', '>', '<', '<', '>', '>', '<' }, // / { '>', '>', '>', '$', '$', '>', '>', '>' }, // i { '<', '<', '<', '<', '<', '=', '$', '<' }, // ( { '>', '>', '>', '$', '$', '>', '>', '>' }, // ) { '<', '<', '<', '<', '<', '$', '=', '<' }, // # { '>', '>', '>', '<', '<', '>', '>', '<' }, // ^ }; // 算符优先表

/***************************************************************************

* 判断一个符号在算符优先表中位置 *

* @param c * @return */

private static int judgePriority(char c) {

}

int priority = 0; switch (c) { case '+':

priority = 0; break; case '*':

priority = 1; break; case '/':

priority = 2; break; case 'i':

priority = 3; break; case '(':

priority = 4; break; case ')':

priority = 5; break; case '#':

priority = 6; break; case '^':

priority = 7; break; }

return priority; } /**

* 判断两个算术符的优先级 *

* @param m

* 为符号栈的栈顶元素 * @param n

* 为当前输入算术符 * @return */

public static char getPriority(char m, char n) {

return PriorityTable.table[judgePriority(m)][judgePriority(n)]; }

二、根据算符优先表用栈结构来实现算符优先分析

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库王鸿百学年论文在线全文阅读。