编译原理

list -> list + digit
list -> list - digit
list -> digit
digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

list -> list + digit | list - digit | digit
digit -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

call -> id ( optparams )
optparams -> params | ε
params -> params , param | param

string = string + string | string - string | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

left -> left op id | id

right -> id op right | id

expr -> expr + term | expr - term | term
term -> term * factor | term / factor | factor
factor -> digit | (expr)

stmt -> expr;
        |   if(expr) stmt
        |   for(optexpr; optexpr;optexpr) stmt
        |   other
optexpr -> ε
        |   expr

for(;expr;expr) other

A -> γR
R -> αR | βR | ε

expr -> expr + term
    |   expr - term
    |   term
term -> 1|2|3|4|5|6|7|8|9|0

expr -> term rest
rest -> + term rest
    |   - term rest
    |   ε
term -> 1|2|3|4|5|6|7|8|9|0

package cn.rectcircle.dragonbook.ch02;

import java.io.IOException;

/**
 * 十以内自然数+-法 原始文法
 *
 * <pre>
 * expr -> expr + term
 *      |   expr - term
 *      |   term
 * term -> 1|2|3|4|5|6|7|8|9|0
 * </pre>
 *
 * 消除左递归后的文法
 *
 * <pre>
 * expr -> term rest
 * rest -> + term rest
 *      |  - term rest
 *      |  ε
 * term -> 1|2|3|4|5|6|7|8|9|0
 * </pre>
 */
class Parser {
	static int lookahead;

	public Parser() throws IOException {
		lookahead = System.in.read();
	}

	/**
	 * 非终结符号expr
	 */
	void expr() throws IOException {
		term();
		rest();
	}

	/**
	 * rest
	 */
	void rest() throws IOException {
		// 尾递归，可以优化为循环
		if (lookahead=='+'){
			match('+'); term(); System.out.print('+'); rest();
		} else if(lookahead=='-'){
			match('-'); term(); System.out.print('-'); rest();
		} else if(lookahead=='\n' || lookahead == -1) { // 相当于空串 ε 流式处理的终结符
			return;
		} else {
			throw new Error("syntax error");
		}
	}

	/**
	 * 终结符号数字
	 */
	void term() throws IOException {
		if(Character.isDigit((char) lookahead)){
			System.out.write((char) lookahead); match(lookahead);
		} else {
			throw new Error("syntax error");
		}
	}

	/**
	 * 移动游标
	 */
	void match(int t) throws IOException {
		if (lookahead==t) lookahead = System.in.read();
		else throw new Error("syntax error");
	}
}

/**
 * 解析10以内自然数加减法是否存在语法错误，并转换为后缀表达式并输出
 */
public class Postfix {
	public static void main(String[] args) throws IOException {
		Parser parser = new Parser();
		parser.expr();
		System.out.println();
	}
}

expr -> expr + term
    |   expr - term
    |   term

term -> term * factor
    |   term / factor
    |   factor

factor -> (expr)
      |   num
      |   id

package cn.rectcircle.dragonbook.ch02.lexer;

/**
 * Token词法单元父类
 */
public class Token {
	public final int tag;

	public Token(int tag) {
		this.tag = tag;
	}
}

package cn.rectcircle.dragonbook.ch02.lexer;

/**
 * 标签枚举
 */
public class Tag {
	public final static int NUM = 256;
	public final static int ID = 257;
	public final static int TRUE = 258;
	public final static int FALSE = 259;
}

package cn.rectcircle.dragonbook.ch02.lexer;

/**
 * 数字词素
 */
public class Num extends Token{
	public final int value;

	public Num(int value) {
		super(Tag.NUM);
		this.value = value;
	}
}

package cn.rectcircle.dragonbook.ch02.lexer;

/**
 * 关键字or保留字词素
 */
public class Word extends Token {
	public final String lexeme;

	public Word(int tag, String lexeme) {
		super(tag);
		this.lexeme = lexeme;
	}
}

package cn.rectcircle.dragonbook.ch02.lexer;

import java.io.IOException;
import java.util.HashMap;
import java.util.Map;

/**
 * 四则运算词法分析器，实现的文法如下
 *
 * <pre>
expr -> expr + term
    |   expr - term
    |   term

term -> term * factor
    |   term / factor
    |   factor

factor -> (expr)
      |   num
      |   id
 * </pre>
 */
public class Lexer {
	public int line = 1;
	private char peek = ' ';
	/**
	 * 关键字/保留字/标识符保持单例
	 */
	private Map<String, Word> words = new HashMap<>();

	public Lexer() {
		reserve(new Word(Tag.TRUE, "true"));
		reserve(new Word(Tag.FALSE, "false"));
	}

	/**
	 * 将关键字词/标识符素放入
	 */
	private void reserve(Word t) {
		words.put(t.lexeme, t);
	}

	public Token scan() throws IOException {
		// 处理多余空白字符
		for (;; peek = (char) System.in.read()) {
			if (peek == ' ' || peek == '\t') {
				continue;
			} else if (peek == '\n') {
				line++;
			} else {
				break;
			}
		}
		// 下面根据第一个有效字符的情况进行预读
		// 第一个字符是数字：解析成int
		if (Character.isDigit(peek)) {
			int v = 0;
			do {
				v = 10 * v + Character.digit(peek, 10);
				peek = (char) System.in.read();
			} while (Character.isDigit(peek));
			return new Num(v);
		}
		// 第一个字符是字母
		if (Character.isLetter(peek)) {
			StringBuilder sb = new StringBuilder();
			do {
				sb.append(peek);
				peek = (char) System.in.read();
			} while (Character.isLetterOrDigit(peek));
			String s = sb.toString();
			Word w = words.get(s);
			if (w != null) {
				return w;
			}
			w = new Word(Tag.ID, s);
			reserve(w);
			return w;
		}
		Token t = new Token(peek);
		peek = ' ';
		return t;
	}

}

package cn.rectcircle.dragonbook.ch02.symbols;

/**
 * 符号
 */
public class Symbol {

}

package cn.rectcircle.dragonbook.ch02.symbols;

import java.util.HashMap;
import java.util.Map;

/**
 * 符号表（作用域），是一个树形结构。 每个符号表为一个节点，其存在一个指向父节点（上层作用域）的指针
 */
public class Env {
	private Map<String, Symbol> table;
	protected Env prev;

	public Env(Env prev) {
		this.table = new HashMap<>();
		this.prev = prev;
	}

	public void put(String s, Symbol sym) {
		table.put(s, sym);
	}

	public Symbol get(String s) {
		for (Env e = this; e != null; e = e.prev) {
			Symbol sym = e.table.get(s);
			if (sym != null) {
				return sym;
			}
		}
		return null;
	}

}

program -> block
block   -> '{' stmts '}'
stmts   -> stmts stmt
        |  ε
stmt    -> expr;
        |  if (expr) stmt
        |  while (expr) stmt
        |  do stmt while(expr);
        |  block
expr    -> rel = expr
        |  rel
rel     -> rel < add
        |  rel <= add
        |  add
add     -> add + term
        |  term
term    -> term * factor
        |  factor
factor  -> (expr)
        |  num

x = y op z

x[y] = z
x = y[z]

ifFalse x goto  L
ifTrue x goto  L
goto L

x = y

letter_ -> A|B|C|...|Z|a|b|...|z|_
digit   -> 0|1|2|...|9
id      -> letter_(letter_|digit)*

letter_ -> [A-Za-z_]
digit   -> [0-9]
id      -> letter_(letter_|digit)*

b = "ababaa";
t = 0; // 前缀的长度（下一个字符的下标）
f[1] = 0;
for(int s=1; s<n; s++){ // 此s表示b的下标（从0开始）
	while(t>0 && b[s] != b[t]) t = f[t]; //找到一个最长前缀==后缀，直到长度为0。
	if(b[s] == b[t]){ t=t+1; f[s+1] = t;} // 如果t==0 此句不执行
	else f[s+1] = 0;
}

a = "fabababaa";
s = 0;
for(int i=0; 0<m; i++){
	while(s>0 && a[i] != b[s]) s = f[s];  //发生失配，一直进行回退，直到s==0
	if(a[i] == b[s]) s = s + 1; // 如果回退到了s==0，此不执行，直接跳到i++
	if(s == n) return i;
}
return -1;

Dstates = {ε-closure(s0)} // 不添加标记
while(Dstates中存在未标记的元素){
	T = Dstates中未标记的元素
	for(针对每个输入符号){
		U = ε-closure(move(T,a))
		if(U not in Dstates)
			将U添加到Dstates中并不添加标记
		DTran[T, a] =U
	}
}

S = ε-closure(s0)
c = nextC()
while(c != eof){
	S = c-closure(move(S,c))]
	c = nextChar()
}
if( |S∩F| != 0) return true
else return false