정규식을 NFA로 변환하려고하는데 문제가 있습니다. 당신이 그 주제에 대해 알지 못한다면 이것은 내가 말하고있는 것에 대한 링크입니다 here.정규 표현식을 구문 분석하는 동안 오토 마타를 만듭니다.
여기에서 문제는 작성자가 주어진 문자열을 먼저 접미사로 변환한다고 설명하는 것입니다. 그는 실시간으로 R.E를 파싱하는 동안 NFA를 그리는 것이 더 좋을 것이라고 언급하지만 그러한 방법을 제공하지 않았습니다 .....
시작시 문제가 있습니다. 아무도 그들이 괄호 큰 문제가 있기 때문에 먼저 수행해야하기 때문에 문자열을 구문 분석하는 동안 NFA를 만드는 알고리즘을해야합니다 안내해 주시겠습니까 ......
추신 : 나는 실제로 이 태그에 어떤 태그를 추가해야합니까? 또한 숙제가 아닙니다.
여기 파이썬의 한 페이지에 a combined parser, NFA builder, and NFA interpreter이 있습니다. 나는 너 자신을 위해 그것을 알아내는 즐거움을 망치고 있지 않다는 것을 희망한다 - 당신은 링크를 따라 가기 전에 해킹을 기다리고 선호하는 편이 낫다.
그것은 deinst의 제안과 비슷하지만 '거꾸로'입니다. deinst가 말했듯이 파서가 정규 표현식의 각 하위 표현식에 대해 NFA를 작성한 다음 이동하면서 그 구문을 연결시킬 수 있습니다. 예를 들어 (a|b)*c의 경우 (a|b)*을 구문 분석하여 NFA # 1을 얻은 다음 c을 구문 분석하여 NFA # 2를 가져온 다음 NFA # 1의 최종 상태를 복제하여 # 2의 시작 상태로 변경합니다. 그리고 재귀 적으로. 이것은 일반적인 대답입니다.
대신 내 코드는 처음에는 수락 상태만으로 간단한 NFA를 만듭니다. 그런 다음 NFA를 확장하여 c을 구문 분석합니다. 이제는 c을 확인한 다음 NFA를 수락합니다. 그런 다음 NFA를 계속 확장하면서 (a|b)*을 반복적으로 구문 분석합니다. 문자열 re 및 NFA k이 제공된 파서의 계약은 re이 일치 할 때 k의 시작 부분에서 끝나는 결과 NFA를 생성하기 위해 문자열을 구문 분석하는 것입니다. 이 접근법은 부분적인 NFA의 비트를 서로 얽히게 할 필요가 없도록합니다.
괄호 안의 정규 표현식을 별도의 NFA로 간주 할 수 있습니다. 당신이 신경 쓰는 것은 그것이 입력 상태와 승인 상태를 가지고 있다는 것입니다. 재귀 적으로 괄호 안의 내용을 NFA로 구문 분석하고 입력을 연결하고 상태를 사용자가 구성중인 NFA의 적절한 위치에 수락합니다. 중위 표현식을 파싱하는 까다로운 부분은 연산자 우선 순위가 정확 해지고 후위로 변환하는 것만큼이나 많은 작업이 소요됩니다.
나는 그가 의미하는 바는 후위를 출력하는 대신에 (shunting yard algorithm에서), 후위를 재분석하는 대신 후치 토큰을 (출력하는 대신) 출력 할 준비가 될 때 처리하는 것입니다.
이것은 귀하의 질문에 대답하지 않지만 저자 (Russ Cox)가 그 기사에서 아이디어를 구현 한 것을 보았습니까? http://code.google.com/p/re2/ –