우선순위가 있는 방정식(표현식) 파서?
https://stackoverflow.com/questions/28256
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
저는 이진(+, -, |, &, *, / 등) 연산자, 단항(!) 연산자 및 괄호를 처리하는 간단한 스택 알고리즘을 사용하여 방정식 파서를 개발했습니다.
그러나 이 방법을 사용하면 모든 것이 동일한 우선 순위를 가지게 됩니다. 괄호를 사용하여 우선 순위를 적용할 수 있지만 연산자에 관계없이 왼쪽에서 오른쪽으로 평가됩니다.
따라서 현재 "1+11*5"는 예상한 대로 56이 아닌 60을 반환합니다.
이는 현재 프로젝트에 적합하지만 이후 프로젝트에 사용할 수 있는 범용 루틴을 갖고 싶습니다.
명확성을 위해 편집됨:
우선순위가 있는 방정식을 분석하기 위한 좋은 알고리즘은 무엇입니까?
나는 사용 가능한 코드의 라이센스 문제를 피하기 위해 직접 코딩할 수 있다는 것을 구현하고 이해하기 쉬운 것에 관심이 있습니다.
문법:
문법 문제를 이해하지 못합니다. 제가 직접 작성했습니다.YACC나 Bison이 필요하지 않을 정도로 간단합니다."2+3 * (42/13)"과 같은 방정식을 사용하여 문자열을 계산하면 됩니다.
언어:
저는 이 작업을 C로 하고 있지만 언어별 솔루션이 아닌 알고리즘에 관심이 있습니다.C는 필요한 경우 다른 언어로 쉽게 변환할 수 있을 정도로 수준이 낮습니다.
코드 예
나는 단순 표현식 파서의 테스트 코드 위에서 얘기했거든요.프로젝트 요구 사항이 변경되었으므로 코드가 프로젝트에 통합되지 않았기 때문에 성능이나 공간을 위해 코드를 최적화할 필요가 없었습니다.원래의 장황한 형식이므로 쉽게 이해할 수 있어야 합니다.연산자 우선 순위 측면에서 추가 작업을 수행하면 아마도 다음을 선택할 것입니다. 매크로 해킹 단순성 측면에서 프로그램의 나머지 부분과 일치하기 때문입니다.하지만 실제 프로젝트에서 이것을 사용하게 된다면 좀 더 컴팩트하고 빠른 파서를 사용하게 될 것입니다.
관련 질문
-아담
해결책
어려운 방법
당신은 재귀 하강 파서.
우선순위를 얻으려면 예를 들어 샘플 문자열을 사용하여 재귀적으로 생각해야 합니다.
1+11*5
이 작업을 수동으로 수행하려면 다음을 읽어야 합니다. 1, 그런 다음 플러스를 확인하고 다음으로 시작하는 완전히 새로운 재귀 구문 분석 "세션"을 시작합니다. 11...그리고 구문 분석을 확인하십시오 11 * 5 자체 요소로 변환하여 다음과 같은 구문 분석 트리를 생성합니다. 1 + (11 * 5).
특히 C의 무력함이 추가되면서 이 모든 것은 설명하려고 시도하는 것조차 너무 고통스럽습니다.11을 구문 분석한 후 *가 실제로 +인 경우 용어를 만드는 시도를 포기하고 대신 다음을 구문 분석해야 합니다. 11 그 자체가 하나의 요인이 됩니다.내 머리는 이미 폭발하고 있습니다.재귀적인 괜찮은 전략으로 가능하지만 더 좋은 방법이 있습니다 ...
쉬운 (올바른) 방법
Bison과 같은 GPL 도구를 사용하는 경우 Bison이 생성한 C 코드는 GPL에 포함되지 않으므로 라이센스 문제에 대해 걱정할 필요가 없습니다. (IANAL이지만 GPL 도구는 GPL을 강제로 적용하지 않는다고 확신합니다. 생성된 코드/바이너리;예를 들어 Apple은 Aperture와 같은 코드를 GCC로 컴파일하고 해당 코드를 GPL하지 않고도 판매합니다.
들소 다운로드 (또는 이에 상응하는 것, ANTLR 등).
일반적으로 bison을 실행하고 이 네 가지 기능 계산기를 보여주는 원하는 C 코드를 얻을 수 있는 몇 가지 샘플 코드가 있습니다.
http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html
생성된 코드를 보고 이것이 말처럼 쉽지 않다는 것을 확인하십시오.또한 Bison과 같은 도구를 사용하면 1) 무언가를 배울 수 있고(특히 Dragon 책을 읽고 문법을 배울 경우), 2) 피할 수 있습니다. NIH : 국립보건원 바퀴를 재발 명하려고합니다.실제 파서 생성기 도구를 사용하면 실제로 나중에 확장하여 파서가 파싱 도구의 영역이라는 것을 다른 사람들에게 보여줄 수 있다는 희망이 있습니다.
업데이트:
이곳 사람들은 많은 건전한 조언을 해주었습니다.구문 분석 도구를 건너뛰거나 Shunting Yard 알고리즘 또는 손으로 굴린 재귀 괜찮은 파서를 사용하는 것에 대한 유일한 경고는 작은 장난감 언어입니다.1 언젠가는 함수(sin, cos, log)와 변수, 조건, for 루프를 갖춘 거대한 실제 언어로 바뀔 수도 있습니다.
Flex/Bison은 작고 간단한 인터프리터에 비해 과잉일 수 있지만 일회성 파서와 평가기는 변경이 필요하거나 기능을 추가해야 할 때 문제를 일으킬 수 있습니다.귀하의 상황은 다양하므로 판단을 내려야 합니다.그냥하지 마세요 당신의 죄에 대해 다른 사람들을 처벌하십시오 [2] 적절하지 않은 도구를 구축하십시오.
내가 가장 좋아하는 구문 분석 도구
작업을 위한 세상에서 가장 좋은 도구는 파섹 프로그래밍 언어 Haskell과 함께 제공되는 라이브러리(재귀적 괜찮은 파서용)입니다.많이 닮았어 BNF, 또는 구문 분석을 위한 일부 특수 도구나 도메인 특정 언어(샘플 코드 [3])와 비슷하지만 실제로는 Haskell의 일반 라이브러리일 뿐입니다. 즉, 나머지 Haskell 코드와 동일한 빌드 단계에서 컴파일된다는 의미입니다. 임의의 Haskell 코드를 작성하고 이를 파서 내에서 호출할 수 있으며, 다른 라이브러리를 혼합하고 일치시킬 수 있습니다. 모두 같은 코드로.(그런데 하스켈이 아닌 다른 언어에 이와 같은 구문 분석 언어를 삽입하면 구문이 너무 복잡해집니다.C#에서 이 작업을 수행했는데 꽤 잘 작동하지만 그렇게 예쁘거나 간결하지는 않습니다.)
노트:
1 리처드 스톨먼은 이렇게 말했습니다. Tcl을 사용하면 안되는 이유
EMAC의 주요 교훈은 확장 언어가 단순한 "확장 언어"가되어서는 안된다는 것입니다.실질적인 프로그램을 작성하고 유지하도록 설계된 실제 프로그래밍 언어 여야합니다.사람들은 그렇게하고 싶어하기 때문입니다!
[2] 네, 저는 그 "언어"를 사용함으로써 영원히 상처를 입었습니다.
또한 이 항목을 제출했을 때 미리보기는 정확했지만 SO가 적절하지 않은 파서가 첫 번째 단락에서 내 가까운 앵커 태그를 먹었습니다., 정규식과 일회성 해킹을 사용하면 파서가 사소한 것이 아니라는 것을 증명합니다. 아마도 미묘하고 작은 문제가 생길 것입니다..
[3] Parsec을 사용하는 Haskell 파서의 일부:지수, 괄호, 곱셈을 위한 공백, 상수(예: pi 및 e)로 확장된 4가지 기능 계산기입니다.
aexpr = expr `chainl1` toOp
expr = optChainl1 term addop (toScalar 0)
term = factor `chainl1` mulop
factor = sexpr `chainr1` powop
sexpr = parens aexpr
<|> scalar
<|> ident
powop = sym "^" >>= return . (B Pow)
<|> sym "^-" >>= return . (\x y -> B Pow x (B Sub (toScalar 0) y))
toOp = sym "->" >>= return . (B To)
mulop = sym "*" >>= return . (B Mul)
<|> sym "/" >>= return . (B Div)
<|> sym "%" >>= return . (B Mod)
<|> return . (B Mul)
addop = sym "+" >>= return . (B Add)
<|> sym "-" >>= return . (B Sub)
scalar = number >>= return . toScalar
ident = literal >>= return . Lit
parens p = do
lparen
result <- p
rparen
return result
다른 팁
shunting yard 알고리즘 이이를위한 올바른 도구입니다. Wikipedia는 이것에 대해 정말 혼란 스럽지만 기본적으로 알고리즘은 다음과 같이 작동합니다.
1 + 2 * 3 + 4를 평가하고 싶다고 말해보세요. 직관적으로 2 * 3을 먼저해야한다는 것을 "알고"있지만이 결과는 어떻게 얻습니까? 핵심은 문자열을 왼쪽에서 오른쪽으로 스캔 할 때 따르는 연산자가 더 낮은 (또는 같음) 우선 순위를 가질 때 연산자를 평가한다는 것을 인식하는 것입니다. 예의 맥락에서 수행 할 작업은 다음과 같습니다.
- 보기 : 1 + 2, 아무것도하지 마세요.
- 이제 1 + 2 * 3을보세요. 여전히 아무것도하지 않습니다.
- 이제 1 + 2 * 3 + 4를 살펴보면 다음 연산자의 우선 순위가 더 낮기 때문에 2 * 3을 평가해야한다는 것을 알 수 있습니다.
이것을 어떻게 구현합니까?
두 개의 스택 (하나는 숫자 용, 다른 하나는 연산자 용)이 필요합니다. 항상 스택에 숫자를 넣습니다. 각각의 새 연산자를 스택의 맨 위에있는 연산자와 비교합니다. 스택 맨 위에있는 연산자가 더 높은 우선 순위를 갖는 경우 연산자 스택에서 제거하고 숫자 스택에서 피연산자를 제거하고 연산자를 적용하고 결과를 푸시합니다. 숫자 스택에. 이제 스택 상단 연산자로 비교를 반복합니다.
이 예제로 돌아 가면 다음과 같이 작동합니다.
N= [] 작업= []
- 1을 읽습니다. N= [1], Ops= []
- +를 읽어보세요. N= [1], 작업= [+]
- 2를 읽습니다. N= [1 2], Ops= [+]
-
*를 읽습니다. N= [1 2], 작업= [+ *] - 3을 읽습니다. N= [1 2 3], Ops= [+ *]
- +를 읽어보세요. N= [12 3], 작업= [+ *]
- 3, 2를 팝하고 2
*3을 실행하고 결과를 N에 푸시합니다. N= [1 6], Ops= [+] -
+는 연관성이 있으므로 1, 6도 빼고 +를 실행하려고합니다. N= [7], 작업= []. - 마지막으로 [+]를 연산자 스택으로 밀어 넣습니다. N= [7], 작업= [+].
- 4를 읽습니다. N= [7 4]. 작업= [+].
- 입력이 부족하므로 지금 스택을 비우고 싶습니다. 결과 11을 얻을 수 있습니다.
그렇게 어렵지 않습니까? 그리고 문법이나 파서 생성기를 호출하지 않습니다.
- 3, 2를 팝하고 2
http://www.engr.mun.ca/~theo/Misc / exp_parsing.htm
다양한 접근 방식에 대한 아주 좋은 설명 :
- 재귀 하강 인식
- 분로 장 알고리즘
- 클래식 솔루션
- 우선 등반
간단한 언어와 의사 코드로 작성되었습니다.
저는 '우선 등반'을 좋아합니다.
간단한 재귀 하강 파서를 연산자와 결합하는 방법에 대한 여기 가 있습니다.우선 순위 구문 분석.최근에 파서를 작성했다면 읽기가 매우 흥미롭고 유익 할 것입니다.
오래 전에 나는 파싱에 관한 책 (Dragon Book과 같은)에서 찾을 수 없었던 나만의 파싱 알고리즘을 만들었습니다. Shunting Yard 알고리즘에 대한 포인터를 살펴보면 유사점이 보입니다.
약 2 년 전에 http :에 Perl 소스 코드가 포함 된 게시물을 올렸습니다. //www.perlmonks.org/?node_id=554516 . 다른 언어로 이식하는 것은 쉽습니다. 제가 한 첫 번째 구현은 Z80 어셈블러에서 이루어졌습니다.
숫자를 사용한 직접 계산에 이상적이지만 필요한 경우 파스 트리를 생성하는 데 사용할 수 있습니다.
업데이트 더 많은 사람들이 자바 스크립트를 읽거나 실행할 수 있기 때문에 코드가 재구성 된 후 자바 스크립트로 파서를 다시 구현했습니다. 전체 파서는 오류보고 및 주석을 포함하여 5k 미만의 자바 스크립트 코드 (파서의 경우 약 100 줄, 래퍼 기능의 경우 15 줄) 미만입니다.
http://users.telenet.be/bartl에서 라이브 데모를 찾을 수 있습니다. /expressionParser/expressionParser.html . 라코 디스
현재 구문 분석에 사용중인 문법을 설명 할 수 있다면 도움이 될 것입니다. 문제가있는 것 같습니다.
수정 :
당신이 문법 질문을 이해하지 못하고 '당신이 이것을 손으로 썼다'는 사실은 당신이 '1 + 11 * 5'형식의 표현에 문제가있는 이유를 설명 할 것입니다. 연산자 우선 순위). 예를 들어 '산술 식 문법'을 검색하면 좋은 포인터를 얻을 수 있습니다. 이러한 문법은 복잡 할 필요가 없습니다. 라코 디스
예를 들어 트릭을 수행하고 좀 더 복잡한 표현 (예 : 함수 또는 거듭 제곱 등 ...)을 처리하기 위해 사소하게 확장 될 수 있습니다.
예를 들어 이 스레드를 살펴 보시기 바랍니다.
문법 / 파싱에 대한 거의 모든 소개는 산술 표현을 예로 취급합니다.
문법을 사용한다고해서 특정 도구 ( a la Yacc, Bison, ...)를 사용하는 것은 아닙니다. 실제로 이미 다음과 같은 문법을 사용하고 계실 것입니다. 라코 디스
(또는 어떤 종류의) 모르는 사이에!
Boost Spirit 사용에 대해 생각해 보셨습니까?다음과 같이 C ++로 EBNF와 유사한 문법을 작성할 수 있습니다. 라코 디스
질문을 넣으면 재귀가 전혀 필요하지 않습니다. 답은 세 가지입니다. Postfix 표기법, Shunting Yard 알고리즘 및 Postfix 표현식 평가 :
1). 후위 표기법= 명시적인 우선 순위 지정이 필요하지 않도록 고안되었습니다. 인터넷에서 더 많은 것을 읽으십시오. 그러나 여기에 그것의 요점이 있습니다 : infix expression (1 + 2) * 3 인간이 읽고 처리하기 쉽지만 기계를 통한 컴퓨팅에는 그리 효율적이지 않습니다. 뭐가? "우선적으로 캐싱하여 표현식을 다시 작성하고 항상 왼쪽에서 오른쪽으로 처리"라는 간단한 규칙입니다. 따라서 infix (1 + 2) * 3은 postfix 12 + 3 *이됩니다. 연산자는 항상 피연산자 뒤에 위치하므로 POST.
2). 접미사 표현 평가. 쉬운. 접미사 문자열에서 숫자를 읽습니다. 작업자가 보일 때까지 스택에 밀어 넣으십시오. 연산자 유형 확인-단항? 바이너리? 제삼기? 이 연산자를 평가하는 데 필요한만큼 스택에서 피연산자를 팝합니다. 평가하십시오. 결과를 다시 스택에 푸시하십시오! 그리고 거의 끝났습니다. 스택이 하나의 항목= 값을 찾을 때까지 계속하십시오.
후위에있는 (1 + 2) * 3은 "12 + 3 *"입니다. 첫 번째 숫자 읽기= 1. 스택에 밀어 넣습니다. 다음을 읽으십시오. 번호= 2. 스택에 밀어 넣습니다. 다음을 읽으십시오. 운영자. 어느 것? +. 어떤 종류? Binary= 두 개의 피연산자가 필요합니다. 스택 두 번 팝= argright는 2이고 argleft는 1입니다. 1 + 2는 3입니다. 3을 스택에 다시 밀어 넣습니다. 접미사 문자열에서 다음을 읽습니다. 그 숫자. 3. 푸시. 다음을 읽으십시오. 운영자. 어느 것? *. 어떤 종류? 바이너리= 두 개의 숫자가 필요-> 두 번 스택. 먼저 argright로, 두 번째로 argleft로 팝합니다. 작업 평가-3 x 3은 9입니다. 스택에 9를 누릅니다. 다음 접미사 문자를 읽으십시오. null입니다. 입력 끝. Pop stack onec= 그게 당신의 대답입니다.
3). Shunting Yard는 인간 (쉽게) 읽을 수있는 중위 식을 접 미식으로 변환하는 데 사용됩니다 (일부 연습 후에 인간이 쉽게 읽을 수 있음). 수동으로 코딩하기 쉽습니다. 위의 주석 및 net을 참조하십시오.
원하는 "일반"정도에 따라 다릅니다.
sin (4 + 5) * cos (7 ^ 3)처럼 수학 함수를 구문 분석 할 수있는 것과 같이 정말 일반적으로 사용하려면 분석 트리
여기에 완전한 구현을 붙여 넣는 것은 적절하지 않다고 생각합니다. 악명 높은 " Dragon book "중 하나를 확인하시기 바랍니다.
하지만 우선 순위 지원 만 원하는 경우 먼저 표현식을 복사하여 붙여 넣을 수있는 알고리즘을 google 또는 코딩 할 수 있다고 생각합니다. 이진 트리로 직접 만들어보세요.
접미사 형태로 있으면 스택이 어떻게 도움이되는지 이미 이해하고 있기 때문에 그때부터 케이크 조각입니다.
Shunting Yard Algorithm 을 속이고 사용하는 것이 좋습니다.간단한 계산기 유형의 파서를 작성하는 쉬운 방법이며 우선 순위를 고려합니다.
적절하게 토큰 화하고 변수 등을 포함하려면 여기에 다른 사람들이 제안한대로 재귀 하강 파서를 작성합니다. 그러나 단순히 계산기 스타일 파서를 필요로한다면이 알고리즘으로 충분합니다.:-)
Shunting Yard 알고리즘 에 대한 PIClist에서 다음을 발견했습니다. <인용구>
Harold의 글 : <인용구>
오래 전에 쉬운 평가를 위해 RPN에 대한 대수 표현식. 각 중위 값 또는 연산자 또는 괄호는 철도 차량으로 표시되었습니다. 과정. 하나 자동차 유형이 다른 트랙으로 분리되고 다른 유형은 계속 똑바로 앞으로. 나는 세부 사항을 기억하지 못하지만 (분명히!) 항상 생각했습니다. 코딩하는 것이 흥미로울 것입니다. 이것은 내가 6800을 쓸 때 돌아 왔습니다. 68000) 어셈블리 코드.
이것이 "shunting yard algorythm"입니다. 대부분의 기계 파서가 사용하다. 파싱에 대한 기사를 참조하십시오. Wikipedia. 쉽게 코딩 할 수있는 방법 shunting yard algorythm은 스택. 하나는 "푸시"스택이고 다른 하나는 "감소"또는 "결과" 스택. 예 :
pstack= () // 빈 rstack= () 입력 : 1 + 2 * 3 우선 순위= 10 // 가장 낮음 reduce= 0 // 줄이지 않음
시작 : 토큰 '1': isnumber, 입력 pstack (푸시) 토큰 '+': isoperator 우선 순위가 <인 경우 우선 순위= 2로 설정 previous_operator_precedence then reduce () // 아래에서 '+'를 넣으십시오. pstack (푸시) 토큰 '2': isnumber, pstack (푸시) 토큰 '*'에 넣습니다. isoperator, 우선 순위= 1 설정, 입력 pstack (push) // 우선 순위 확인 // 토큰 '3'위 : isnumber, 입력 pstack (푸시) 입력 끝, 필요 감소 (목표는 빈 pstack) reduce () // 완료
줄이기 위해 푸시에서 팝 요소 쌓아서 결과에 넣으십시오. 스택, 항상 상위 2 개 항목을 pstack이 형식 인 경우 '연산자' '숫자':
pstack : '1' '+' '2' '' '3'rstack : () ... pstack : () rstack : '3' '2' '' '1' '+'
표현식이 다음과 같을 경우 :
1 * 2 + 3
그러면 감소 트리거는 토큰 '+'를 읽었습니다. 더 낮은 우선 순위를 '*'는 이미 푸시되었으므로 완료 :
pstack : '1' '' '2'rstack : () ... pstack : () rstack : '1' '2' ''
그런 다음 '+'를 누른 다음 '3'을 누르고 마침내 감소 :
pstack : '+' '3'rstack : '1' '2' '' ... pstack : () rstack : '1' '2' '' '3' '+'
짧은 버전은 다음과 같습니다. 숫자 입력, 작업자를 밀 때 이전 연산자의 우선 순위. 운영자보다 높았다면 그것은 지금 밀어 붙이는 것입니다. 줄인 다음 전류를 밀어 운영자. 괄호를 처리하려면 간단히 저장하십시오. '이전'의 우선 순위 연산자, pstack에 표시 그것은 감소 알고리즘을 내부를 해결할 때 감소를 멈추십시오 괄호 쌍의. 닫는 괄호 끝처럼 감소를 유발합니다. 입력, 또한 열린 pstack의 괄호 표시 및 '이전 작업'을 복원합니다. 파싱을 계속할 수 있도록 우선 순위 그것이 떠난 가까운 괄호 뒤에 떨어져서. 이것은 재귀로 할 수 있습니다. 또는없이 (힌트 : 스택을 사용하여 이전 우선 순위 '('...)가 발생했습니다. 그만큼 이것의 일반화 된 버전은 구현 된 파서 생성기 shunting yard algorythm, f.ex. 사용 yacc 또는 bison 또는 taccle (tcl 유사체 yacc).
피터
-아담
초소형 (1 클래스, <10KiB) Java Math Evaluator 내 웹 사이트.이것은 수락 된 답변의 포스터에 두개골 폭발을 일으킨 유형의 재귀 하강 파서입니다.
전체 우선 순위, 괄호, 명명 된 변수 및 단일 인수 함수를 지원합니다.
저는 Dijkstra의 Shunting Yard 알고리즘을 기반으로 한 식 파서를 출시했습니다. Apache 라이선스 2.0 :
우선 순위 파싱을위한 또 다른 리소스는 Wikipedia의 운영자 우선 파서 항목입니다.Dijkstra의 shunting yard 알고리즘과 트리 대체 알고리즘을 다룹니다. 그러나 특히 우선 순위 무지 파서 앞에서 사소하게 구현할 수있는 정말 간단한 매크로 대체 알고리즘을 다룹니다. 라코 디스
다음으로 호출 : 라코 디스
단순함이 훌륭하고 이해하기 쉽습니다.
재귀 하강 파서 를 구현했습니다.http://matheclipse.org/en/MathEclipse_Parser "rel="nofollow noreferrer "> MathEclipse Parser 프로젝트. Google 웹 툴킷 모듈 로도 사용할 수 있습니다.
저는 현재 디자인 패턴과 읽기 쉬운 프로그래밍을위한 학습 도구로 정규 표현식 파서를 구축하는 일련의 기사를 작업 중입니다. 읽을 수있는 코드 를 살펴볼 수 있습니다.이 기사는 shunting yards 알고리즘의 명확한 사용을 제시합니다.
F # 및 블로그에 식 파서를 작성했습니다.여기 .션팅 야드 알고리즘을 사용하지만 중위에서 RPN으로 변환하는 대신 두 번째 스택을 추가하여 계산 결과를 축적했습니다.연산자 우선 순위를 올바르게 처리하지만 단항 연산자는 지원하지 않습니다.이 글은 식 구문 분석을 배우기위한 것이 아니라 F #을 배우기 위해 작성했습니다.
pyparsing을 사용하는 Python 솔루션은 에서 찾을 수 있습니다. 여기 . 우선 순위가있는 다양한 연산자로 중위 표기법을 구문 분석하는 것은 매우 일반적이므로 pyparsing에는 infixNotation (이전의 operatorPrecedence) 표현식 빌더도 포함됩니다. 예를 들어 "AND", "OR", "NOT"등을 사용하여 부울 표현식을 쉽게 정의 할 수 있습니다. 또는!와 같은 다른 연산자를 사용하도록 네 가지 함수 산술을 확장 할 수 있습니다. 계승의 경우 또는 모듈러스의 경우 '%'를 사용하거나 P 및 C 연산자를 추가하여 순열 및 조합을 계산합니다. '-1'또는 'T'연산자 (반전 및 전치) 처리를 포함하는 행렬 표기법을위한 중위 파서를 작성할 수 있습니다. 4 함수 파서의 operatorPrecedence 예 (재미를 위해 '!'가 던져 짐)는 여기 와 더 완전한 기능을 갖춘 파서 및 평가자는 여기 .
나는 이것이 늦은 대답이라는 것을 알고 있지만 모든 연산자 (접두사, 접미사 및 중위 왼쪽, 중위 오른쪽 및 비 연관)가 임의의 우선 순위를 갖도록 허용하는 작은 파서를 작성했습니다.
임의의 DSL을 지원하는 언어로 확장 할 예정이지만 연산자 우선 순위를 위해 사용자 정의 파서가 필요하지 않으며 테이블이 필요없는 일반화 된 파서를 사용할 수 있다는 점을 지적하고 싶었습니다. 모두 표시되고 각 연산자의 우선 순위를 찾습니다. 사람들은 불법 입력을 허용 할 수있는 맞춤형 Pratt 파서 또는 shunting yard 파서를 언급했습니다. 이것은 사용자 정의 할 필요가 없으며 (버그가없는 한) 잘못된 입력을 받아들이지 않습니다. 어떤 의미에서는 완전하지 않으며 알고리즘을 테스트하기 위해 작성되었으며 입력은 전처리가 필요한 형식이지만이를 명확히하는 주석이 있습니다.
인덱싱에 사용되는 연산자 (예 : table [index] 또는 함수 함수 호출 (parameter-expression, ...) 나는 그것들을 추가 할 것이지만, 둘 다 구분자 '['와 ']'또는 '('와 ')'사이에 오는 것이 표현 파서의 다른 인스턴스로 구문 분석되는 접미사 연산자로 생각합니다. 생략해서 죄송하지만 접미사 부분이 있습니다. 나머지를 추가하면 코드 크기가 거의 두 배가 될 것입니다.
파서는 단지 100 줄의 라켓 코드이므로 여기에 붙여 넣어야합니다. 이것이 stackoverflow가 허용하는 것보다 길지 않기를 바랍니다.
임의의 결정에 대한 몇 가지 세부 정보 :
낮은 우선 순위 접두사 연산자가 낮은 우선 순위 접두사 연산자와 동일한 중위 블록에 대해 경쟁하는 경우 접두사 연산자가 이깁니다. 대부분의 언어에는 우선 순위가 낮은 접미사 연산자가 없기 때문에 이것은 대부분의 언어에서 나오지 않습니다. -예 : ((data a) (left 1 +) (pre 2 not) (data b) (post 3!) (left 1 +) (data c)) a + not b! + c 여기서 not은 접두사 연산자이고! 후위 연산자이며 둘 다 더 낮습니다. +보다 우선 순위가 높으므로 다음과 같이 호환되지 않는 방식으로 그룹화하려고합니다. (a + b 아님!) + c 또는 a + (b! + c 아님) 이 경우 접두사 연산자가 항상이기므로 두 번째는 구문 분석 방식입니다.
비 연관 중위 연산자는 실제로 존재하므로 서로 다른 유형을 반환하는 연산자가 합리적이라고 생각할 필요가 없지만 각각에 대해 다른 표현식 유형을 갖지 않으면 문제가됩니다. 따라서이 알고리즘에서 비 연관 연산자는 자신뿐만 아니라 동일한 우선 순위를 가진 연산자와의 연관을 거부합니다. <<===>= 등은 대부분의 언어에서 서로 연관되지 않기 때문에 일반적인 경우입니다.
다른 유형의 연산자 (왼쪽, 접두사 등)가 우선 순위에서 어떻게 연결을 끊는 지에 대한 질문은 다른 유형의 연산자에 동일한 우선 순위를 부여하는 것이 실제로 이치에 맞지 않기 때문에 발생해서는 안됩니다. 이 알고리즘은 이러한 경우에 뭔가를 수행하지만, 그러한 문법은 애초에 나쁜 생각이기 때문에 정확히 무엇을 알아내는 데 신경 쓰지 않습니다. 라코 디스
다음은 Java로 작성된 간단한 케이스 재귀 솔루션입니다.음수를 처리하지 않지만 원하는 경우 추가 할 수 있습니다. 라코 디스
}
알고리즘은 재귀 하강 파서로 C에서 쉽게 인코딩될 수 있습니다.
#include <stdio.h>
#include <ctype.h>
/*
* expression -> sum
* sum -> product | product "+" sum
* product -> term | term "*" product
* term -> number | expression
* number -> [0..9]+
*/
typedef struct {
int value;
const char* context;
} expression_t;
expression_t expression(int value, const char* context) {
return (expression_t) { value, context };
}
/* begin: parsers */
expression_t eval_expression(const char* symbols);
expression_t eval_number(const char* symbols) {
// number -> [0..9]+
double number = 0;
while (isdigit(*symbols)) {
number = 10 * number + (*symbols - '0');
symbols++;
}
return expression(number, symbols);
}
expression_t eval_term(const char* symbols) {
// term -> number | expression
expression_t number = eval_number(symbols);
return number.context != symbols ? number : eval_expression(symbols);
}
expression_t eval_product(const char* symbols) {
// product -> term | term "*" product
expression_t term = eval_term(symbols);
if (*term.context != '*')
return term;
expression_t product = eval_product(term.context + 1);
return expression(term.value * product.value, product.context);
}
expression_t eval_sum(const char* symbols) {
// sum -> product | product "+" sum
expression_t product = eval_product(symbols);
if (*product.context != '+')
return product;
expression_t sum = eval_sum(product.context + 1);
return expression(product.value + sum.value, sum.context);
}
expression_t eval_expression(const char* symbols) {
// expression -> sum
return eval_sum(symbols);
}
/* end: parsers */
int main() {
const char* expression = "1+11*5";
printf("eval(\"%s\") == %d\n", expression, eval_expression(expression).value);
return 0;
}
다음 라이브러리가 유용할 수 있습니다. 유파나 - 엄격한 산술 연산 작은익스프레 - 산술 연산 + C 수학 함수 + 사용자가 제공하는 함수; mpc - 파서 결합자
설명
대수적 표현을 나타내는 일련의 기호를 포착해 보겠습니다.첫 번째는 숫자, 즉 한 번 이상 반복되는 십진수입니다.우리는 이러한 표기법을 생산 규칙이라고 부를 것입니다.
number -> [0..9]+
피연산자가 있는 덧셈 연산자는 또 다른 규칙입니다.그것은 둘 중 하나이다 number 또는 이를 나타내는 기호 sum "*" sum 순서.
sum -> number | sum "+" sum
대체해 보세요 number ~ 안으로 sum "+" sum 그럴 것이다 number "+" number 이는 다시 다음으로 확장될 수 있습니다. [0..9]+ "+" [0..9]+ 마침내 다음과 같이 줄어들 수 있습니다. 1+8 올바른 덧셈 표현입니다.
다른 대체도 올바른 표현을 생성합니다. sum "+" sum -> number "+" sum -> number "+" sum "+" sum -> number "+" sum "+" number -> number "+" number "+" number -> 12+3+5
조금씩 우리는 일련의 생산 규칙과 유사할 수 있습니다. 일명 문법 가능한 모든 대수적 표현을 표현합니다.
expression -> sum
sum -> difference | difference "+" sum
difference -> product | difference "-" product
product -> fraction | fraction "*" product
fraction -> term | fraction "/" term
term -> "(" expression ")" | number
number -> digit+
연산자 우선순위를 제어하려면 다른 연산자에 대한 생성 규칙의 위치를 변경하십시오.위의 문법을 보고 * 아래에 배치되어 있습니다 + 이것은 강제로 product 전에 평가하다 sum.구현은 패턴 인식과 평가를 결합하여 생산 규칙을 밀접하게 반영합니다.
expression_t eval_product(const char* symbols) {
// product -> term | term "*" product
expression_t term = eval_term(symbols);
if (*term.context != '*')
return term;
expression_t product = eval_product(term.context + 1);
return expression(term.value * product.value, product.context);
}
여기서 우리는 평가합니다 term 먼저 확인하고, 없으면 반품하세요. * 그 이후의 성격 이것은 우리 생산 규칙에서 선택 사항으로 남아 있습니다 그렇지 않으면 - 이후에 기호를 평가하고 반환합니다. term.value * product.value 이것은 우리의 생산 규칙에서 올바른 선택입니다. term "*" product
