你所要求的是一個編譯器,一個相當複雜的程序,分析在一定的輸入編程語言並將其轉換爲另一種編程語言。
在這種情況下,輸入語言可以是帶數字,標量變量,數組變量,和,乘法和括號的表達式。
輸出語言是帶數字,數組變量,和數,乘法和括號的表達式(注意它不包含標量變量)。
關於編譯器有很多文獻。這是一門跨越計算機科學大學學位課程的學科。
如果您定義了一種非常有限的語言,那麼您可以簡單地進行替換,就像在OP中一樣。但是一旦你開始處理更一般的語言,比如長度大於1的變量,你就需要整個架構來構建一個編譯器。
編譯器有幾個部分:
- 詞法分析器。這打破了TOKENS的輸入。每個令牌都是一個標識符,一個操作符和類似的東西。詞法分析器也從輸入中刪除空白。
- 一個語法分析器。根據TOKENS定義語言的一組規則。經常用context-free grammars完成。
- 語義翻譯器。這可以採用在語法分析器中構建的結構,或者可以在語法分析器中交織。它將輸入語言翻譯爲輸出語言。
- 還有一些其他可選部件,優化程序,超出了這個問題的範圍。
詞法分析器
詞法分析器是打破輸入到令牌。
例如,考慮輸入「3 + a」。
預期令牌是:NUMBER PLUS標識符
我會在正則表達式來定義的標記:
- PLUS:[+]
- 減: -
- 乘法:[* ]
- DIVIDE:/
- NUMBER:[0-9] +
- IDENTIFIER:[A-ZA-Z] +
- OPEN_PARENTHESIS:[(]
- CLOSE_PARENTHESIS:[)]
- OPEN_BRACKET:\ [
- CLOSE_BRACKET:\]
- EOL:對於行尾沒有正則表達式。詞法分析器將在輸入耗盡時返回此標記。
這是詞法分析器的代碼。
首先是一個令牌類,它持有一個令牌,其類型和生成該令牌的輸入的子字符串。
public class Token
{
public static enum TokenType
{
PLUS,
MINUS,
MULTIPLY,
DIVIDE,
NUMBER,
IDENTIFIER,
OPEN_PARENTHESIS,
CLOSE_PARENTHESIS,
OPEN_BRACKET,
CLOSE_BRACKET,
EOL // End of line
}
public Token(TokenType type, String value)
{
this.type = type;
this.value = value;
}
private TokenType type;
public String value;
public TokenType getType()
{
return type;
}
@Override
public String toString()
{
return value;
}
}
接下來是詞法分析器本身。
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import expressionparser.Token.TokenType;
class Tokenizer
{
private final String input;
private Matcher matcher;
private Token lastToken;
public Tokenizer(String input)
{
this.input = input;
Pattern pattern =
Pattern.compile("[+]|-|[*]|/|[0-9]+|[a-zA-Z]+|[(]|[)]|\\[|\\]|[ ]");
matcher = pattern.matcher(input);
lastToken = null;
}
public Token readAndComsumeToken(TokenType type) throws ExpressionException
{
Token result = readToken();
if (result.getType()!=type)
throw new ExpressionException("Erroneous exception");
lastToken = null;
return result;
}
public Token readToken() throws ExpressionException
{
if (lastToken!=null)
return lastToken;
String value;
// Read till a non blank is received
do
{
if (matcher==null)
{
lastToken = new Token(TokenType.EOL, "");
return lastToken;
}
if (!matcher.find())
throw new ExpressionException("Erroneous exception");
value = matcher.group();
if (matcher.end() >= input.length())
{
// End of String
matcher = null;
}
if (value.length()==0)
throw new ExpressionException("Erroneous exception");
} while (value.equals(" ") ||
value.equals("\t") || value.equals("\n") ||
value.equals("\f") || value.equals("\r"));
// Identify read token
TokenType type;
if (value.equals("+"))
type = TokenType.PLUS;
else if (value.equals("-"))
type = TokenType.MINUS;
else if (value.equals("*"))
type = TokenType.MULTIPLY;
else if (value.equals("/"))
type = TokenType.DIVIDE;
else if (value.equals("("))
type = TokenType.OPEN_PARENTHESIS;
else if (value.equals(")"))
type = TokenType.CLOSE_PARENTHESIS;
else if (value.equals("["))
type = TokenType.OPEN_BRACKET;
else if (value.equals("]"))
type = TokenType.CLOSE_BRACKET;
else
{
char firstChar = value.charAt(0);
if (firstChar>='0' && firstChar<='9')
type = TokenType.NUMBER;
else
type = TokenType.IDENTIFIER;
}
lastToken = new Token(type, value);
return lastToken;
}
public void consumeToken() throws IllegalStateException
{
if (lastToken==null)
throw new IllegalStateException();
lastToken = null;
}
}
Tokenizer基於Pattern一個標準的java類,它可以按照正則表達式的規定分解字符串。
構造函數爲輸入表達式創建一個Pattern匹配器。
該模式有一個額外的正則表達式[ ]
未包含在先前的令牌列表中。這會讀取空格,但它們不會被Tokenizer
變成標記,它們將被忽略。
readToken
從匹配器中獲取下一個令牌,忽略空格。它將它保存在lastToken
中,因爲語法分析器可能需要爲相同的標記調用readToken
多次,並且readToken
需要始終返回相同的標記,直到它被使用。如果以前的調用中已經有一個沒有被消費的令牌,它將被返回而不會得到新的令牌。
consumeToken
通過將lastToken
設置爲null
來消耗最後讀取的令牌。在readToken
之前未調用它是錯誤的。
readAndComsumeToken
是一種方便的方法。在某些情況下,語法分析器在讀取它之前會知道下一個標記是什麼。在這種情況下,它需要讀取它,驗證它是否是預期的並使用它。 readAndConsumeToken
在一次通話中完成。
句法分析器。
對於語法分析器首先我們創建一個定義輸入語言的上下文無關語法。
我會用它Backus-Naur Form。
<wholeExpression> ::= <expression> EOL
<expression> ::= <summand> <tailSum>
<summand> ::= <factor> <tailMultiplication>
<factor> ::= OPEN_PARENTHESIS <expression> CLOSE PARENTHESIS |
NUMBER |
IDENTIFIER <tailArray>
<tailSum> ::= PLUS <summand> <tailSum> |
MINUS <summand> <tailSum> |
""
<tailMultiplication> ::= MULTIPLY <factor> <tailMultiplication> |
DIVIDE <factor> <tailMultiplication> |
""
<tailArray> ::= OPEN_BRACKET <expression> CLOSE_BRACKET <tailArray> |
""
實現這樣的語法有幾種方法。甚至有工具可以自動完成。
我將使用Java方法爲語法的每個非終端實現它。它在語義翻譯器中呈現,因爲它與解析器交織在一起。
語義翻譯器。
ExpressionParser
是句法分析器和語義翻譯器的組合。它使用Tokenizer
進行詞法分析。
import expressionparser.Token.TokenType;
import java.util.List;
public class ExpressionParser
{
private Tokenizer lex;
private List<Scalar> scalars;
public String compile(String expression, List<Scalar> scalars) throws ExpressionException
{
lex = new Tokenizer(expression);
this.scalars = scalars;
return evalWholeExpression();
}
private String evalWholeExpression() throws ExpressionException
{
String result = evalExpression();
lex.readAndComsumeToken(Token.TokenType.EOL);
return result;
}
private String evalExpression() throws ExpressionException
{
String left = evalSummand();
return evalTailSum(left);
}
private String evalSummand() throws ExpressionException
{
String left = evalFactor();
return evalTailMultiplication(left);
}
private String evalFactor() throws ExpressionException
{
Token token = lex.readToken();
if (token.getType() == TokenType.OPEN_PARENTHESIS)
{
lex.consumeToken();
String result = evalExpression();
lex.readAndComsumeToken(TokenType.CLOSE_PARENTHESIS);
return "(" + result + ")";
}
else if (token.getType() == TokenType.NUMBER)
{
lex.consumeToken();
return token.toString();
}
else if (token.getType()==TokenType.IDENTIFIER)
{
lex.consumeToken();
String tailArray = evalTailArray();
if ("".equals(tailArray))
{
String scalarValue = evaluateScalar(token.toString());
return scalarValue;
}
else
{
verifyIsNotScalar(token.toString());
return token + tailArray;
}
}
else
throw new ExpressionException("Incorrect expression");
}
private String evalTailSum(String left) throws ExpressionException
{
Token token = lex.readToken();
if (token.getType()==TokenType.PLUS)
{
lex.consumeToken();
String right = evalSummand();
return evalTailSum(left + "+" + right);
}
else if (token.getType()==TokenType.MINUS)
{
lex.consumeToken();
String right = evalSummand();
return evalTailSum(left + "-" + right);
}
else
return left;
}
private String evalTailMultiplication(String left) throws ExpressionException
{
Token token = lex.readToken();
if (token.getType()==TokenType.MULTIPLY)
{
lex.consumeToken();
String right = evalFactor();
return evalTailSum(left + "*" + right);
}
else if (token.getType()==TokenType.DIVIDE)
{
lex.consumeToken();
String right = evalFactor();
return evalTailSum(left + "/" + right);
}
else
return left;
}
private String evalTailArray() throws ExpressionException
{
Token token = lex.readToken();
if (token.getType() == TokenType.OPEN_BRACKET)
{
lex.consumeToken();
String result = evalExpression();
lex.readAndComsumeToken(TokenType.CLOSE_BRACKET);
return "[" + result + "]" + evalTailArray();
}
else
return "";
}
private String evaluateScalar(String text) throws ExpressionException
{
assert text!=null;
for (Scalar s : scalars)
{
if (text.equals(s.identifier))
return "" + s.value;
}
throw new ExpressionException("Incorrect expression");
}
private void verifyIsNotScalar(String text) throws ExpressionException
{
assert text!=null;
for (Scalar s : scalars)
{
if (text.equals(s.identifier))
throw new ExpressionException("Incorrect expression");
}
}
}
compile
創建Tokenizer
詞法分析器的輸入和保存標量的列表。然後它調用evalWholeExpression
,它返回輸入的翻譯,並返回這樣的翻譯。
如果輸入無效,則拋出ExpressionException。這種例外將包含錯誤消息。我沒有努力做出有用的事情。處理錯誤消息本身就是一個完整的主題。
對於我們的上下文無關語法的每個非終端,有一種方法是非終端<。
語法的構成方式是檢查第一個標記足以確定哪個分支要帶有多個選項的非終端。這使得易於創建eval方法。
例如,考慮evalTailSum
。此方法實現這個規則:
<tailSum> ::= PLUS <summand> <tailSum> |
MINUS <summand> <tailSum> |
""
這是單獨使用,並通過這條規則
:
<expression> ::= <summand> <tailSum>
evalExpression
電話evalSummand
並得到一個可能的總和(或減法)左側的翻譯。然後它調用evalTailSum
傳遞它這個翻譯;最後返回它的結果。
<tailSum>有三個分支。
- 一個總是以SUM標記開始的sumation。
- 一個用於總是以MINUS標記開始的減法。
- 否則爲空字符串。對於一組固定的令牌也會發生這種情況。但是這裏沒有必要處理這個問題。
所以evalTailSum
得到lex.readToken()
的下一個標記。然後...
- 如果它是PLUS,它會消耗它。調用
evalSummand
將其結果存儲爲right
。然後調用'evalTailSum'作爲左值left + "+" + right
傳遞給它。請注意令牌消耗和呼叫的順序如何與<tailSum>規則右側的終端和非終端匹配。
- 如果是MINUS,它將遵循與PLUS案例類似的過程。
- 否則,將採用空字符串分支,並返回
left
收到的翻譯作爲結果。
在上下文無關文法中爲每個非終端創建一個方法。
所有這些方法實際上並沒有翻譯得太多。它們產生的輸出與輸入時相同。
但是,對於一個重要的方法,情況並非如此:evalFactor
當它處理標識符分支時,我們需要將變量轉換爲由標量列表指定的值。
實施標量很簡單:
public class Scalar
{
public Scalar(String identifier, int value)
{
this.identifier = identifier;
this.value = value;
}
public final String identifier;
public final int value;
}
在標識符分支evalFactor
消耗標識符並調用evalTailArray
按照在上下文無關文法的<因子>規則。
evalTailArray
如果沒有數組subscrits返回一個空字符串,所以IDENTIFIER必須是一個標量變量。在這種情況下,它調用evaluateScalar
,它在標量列表中搜索該標量並返回其值以便翻譯,或者如果未找到,則會拋出一個ExpressionException。
如果evalTailArray
的結果不是空的,它必須是一個數組。根據OP,我們在這裏沒有翻譯。但是我們通過調用verifyIsNotScalar
來確認沒有這個名稱的標量。如果這種驗證失敗了,這將是一個語義錯誤(如果我們有一個未列出的非數組變量),類似於您可能從C++或Java編譯器中獲得的「未定義變量」或「不兼容類型」錯誤。雖然我們的編譯器拋出的所有其他錯誤都是類似於「syntax error:; expected」的語法錯誤,或者是像「illegal character @」這樣的詞法錯誤。
使用它
這個小程序使用以前的解析器和幾個表情測試它。最後一個是不正確的表達。
import java.util.ArrayList;
import java.util.List;
public class Main
{
public static void main(String[] args)
{
try
{
final List<Scalar> scalars = new ArrayList<>();
scalars.add(new Scalar("a", 1));
scalars.add(new Scalar("b", 2));
scalars.add(new Scalar("d", 3));
scalars.add(new Scalar("varx", 5 ));
ExpressionParser parser = new ExpressionParser();
System.out.println(parser.compile("a - (b+A[B[2]])*d + 3", scalars));
System.out.println(parser.compile("5*(2+varx)+a", scalars));
System.out.println(parser.compile("B[a*384+(5+(5*(varx+3)))]+varx", scalars));
System.out.println(parser.compile("34+", scalars));
}
catch (ExpressionException ex)
{
System.out.println(ex.getMessage());
}
}
}
輸出爲預期:
1-(2+A[B[2]])*3+3
5*(2+5)+1
B[1*384+(5+(5*(5+3)))]+5
Incorrect expression
請提供[SSCCE](http://sscce.org/)。 – mezzodrinker
如果你想要替換一個字符串的值,不要使用String類,因爲String是不可變的,而是使用StringBuffer或StringBuilder.One它比另一個更快,另一個是線程安全。谷歌StringBuffer教程;) –
我不能使用StringBuilder,因爲我不能導入任何東西的任務,不幸的是。 replace()方法是否工作? –