정규 표현의 짧은 예는 상태 기계로 변환 되었습니까?

StackOverflow https://stackoverflow.com/questions/525004

  •  22-08-2019
  •  | 
  •  

문제

스택 오버 플로우 팟 캐스트 #36에서 (http://blog.stackoverflow.com/2009/01/podcast-36/),이 의견은 표현되었습니다. 일단 상태 머신을 설정하는 것이 얼마나 쉬운 지 이해하면 정규 표현식을 다시 부적절하게 사용하려고 시도하지 않을 것입니다.

나는 많은 검색을했다. 학술 논문과 다른 복잡한 사례를 찾았지만이 과정을 이해하는 데 도움이되는 간단한 예를 찾고 싶습니다. 나는 정기적 인 표현을 많이 사용하고 있으며 다시 "부적절하게"사용하지 않도록하고 싶습니다.

도움이 되었습니까?

해결책

물론, RES의 작동 방식을 진정으로 이해하려면 더 복잡한 예가 필요합니다. 다음 Re를 고려하십시오.

^[A-Za-z][A-Za-z0-9_]*$

이는 일반적인 식별자입니다 (알파로 시작해야하며 없음을 포함하여 여러 가지 영숫자 및 Undescore 문자를 가질 수 있습니다). 다음 의사 코드는 유한 상태 기계로 어떻게 수행 할 수 있는지 보여줍니다.

state = FIRSTCHAR
for char in all_chars_in(string):
    if state == FIRSTCHAR:
            if char is not in the set "A-Z" or "a-z":
                error "Invalid first character"
            state = SUBSEQUENTCHARS
            next char
    if state == SUBSEQUENTCHARS:
            if char is not in the set "A-Z" or "a-z" or "0-9" or "_":
                error "Invalid subsequent character"
            state = SUBSEQUENTCHARS
            next char

내가 말했듯이, 이것은 매우 간단한 예입니다. 욕심/비 레디 경기, 역 추적, 라인 내에서 일치하는 방법 (전체 라인 대신) 및 RE 구문이 쉽게 처리 할 수있는 상태 머신의 더 난해한 기능을 보여주는 방법을 보여주지 않습니다.

그래서 RES가 그렇게 강력한 이유입니다. 1 라이너가 할 수있는 일을 수행하는 데 필요한 실제 유한 상태 기계 코드는 일반적으로 매우 길고 복잡합니다.

당신이 할 수있는 가장 좋은 방법은 특정 간단한 언어에 대한 Lex/YACC (또는 동등한) 코드의 사본을 가져 와서 생성하는 코드를 보는 것입니다. 그것은 예쁘지 않습니다 (인간이 읽지 않아야하기 때문에 LEX/YACC 코드를보고 있어야하기 때문에) 그러나 그들이 어떻게 작동하는지에 대한 더 나은 아이디어를 줄 수 있습니다.

다른 팁

파이썬의 거의 알려지지 않은 Re.Debug 플래그를 어떤 패턴으로도 사용하는 데 도움이되는 다소 편리한 방법 :

>>> re.compile(r'<([A-Z][A-Z0-9]*)\b[^>]*>(.*?)</\1>', re.DEBUG)
literal 60
subpattern 1
  in
    range (65, 90)
  max_repeat 0 65535
    in
      range (65, 90)
      range (48, 57)
at at_boundary
max_repeat 0 65535
  not_literal 62
literal 62
subpattern 2
  min_repeat 0 65535
    any None
literal 60
literal 47
groupref 1
literal 62

'문자'및 '범위'이후의 숫자는 그들이 일치 해야하는 ASCII 문자의 정수 값을 나타냅니다.

즉시 직접 만드십시오!

http : //osteele.com/tools/reanimator/ ???

A finite state machine

이것은 정규 표현식을 FSM으로 시각화하는 정말 멋지게 정리 된 도구입니다. 실제 정규 표현 엔진에서 찾을 수있는 구문 중 일부를 지원하지는 않지만 무슨 일이 일어나고 있는지 정확히 이해하기에 충분합니다.

"상태와 전환 조건을 어떻게 선택합니까?"또는 "FOO에서 내 추상 상태 기계를 어떻게 구현합니까?"라는 질문입니까?

상태와 전환 조건을 어떻게 선택합니까?

나는 보통 상당히 간단한 문제를 위해 FSM을 사용하고 직관적으로 선택합니다. ~ 안에 정규 표현에 대한 또 다른 질문에 대한 나의 대답, 나는 방금 구문 분석 문제를 한 사람으로 보았다. Inside 또는 outside 태그 쌍, 그곳에서 전환을 썼습니다 (구현을 깨끗하게 유지하기 위해 시작 및 끝 상태가 포함되어 있음).

FOO에서 추상 상태 기계를 어떻게 구현합니까?

구현 언어가 같은 구조를 지원하는 경우 c'에스 switch 진술, 현재 상태를 켜고 입력을 처리하여 다음에 어떤 동작 및/또는 전환이 수행되는지 확인합니다.

없이 switch-구조와 같은 구조, 또는 어떤 식 으로든 부족한 경우 if 스타일 분기. 어.

한 곳에 모두 작성되었습니다 c 내가 링크 한 예제는 다음과 같이 보일 것입니다.

token_t token;
state_t state=BEGIN_STATE;
do {
   switch ( state.getValue() ) {
   case BEGIN_STATE;
      state=OUT_STATE;
      break;
   case OUT_STATE:
      switch ( token.getValue() ) {
         case CODE_TOKEN:
            state = IN_STATE;
            output(token.string());
            break;
         case NEWLINE_TOKEN;
            output("<break>");
            output(token.string());
            break;
         ...
      }
      break;
   ...
   }
} while (state != END_STATE);

꽤 지저분하므로 나는 보통 찢어집니다. state 별도의 기능으로 사례.

누군가가 더 나은 예를 가지고 있다고 확신하지만 당신은 Phil Haack 의이 게시물을 확인하십시오, 이것은 정규 표현의 예와 같은 일을하는 상태 기계의 예를 가지고 있습니다 (몇 가지 더 많은 재선 예제가있는 이전 게시물이 있습니다.

해당 페이지의 "Henriformatter"를 확인하십시오.

나는 당신이 이미 읽은 학술 논문을 모르지만 실제로 유한 상태 기계를 구현하는 방법을 이해하는 것은 어렵지 않습니다. 흥미로운 수학이 있지만 아이디어는 실제로 이해하기가 매우 사소합니다. FSM을 이해하는 가장 쉬운 방법은 입력 및 출력을 통하는 것입니다 (실제로는 여기에 설명하지 않는 대부분의 공식 정의로 구성됩니다). "상태"는 본질적으로 일련의 입력 및 출력 세트를 설명하고 특정 지점에서 발생할 수 있습니다.

유한 상태 기계는 다이어그램을 통해 이해하기 가장 쉽습니다. 예를 들어:

Alt Text http://img6.imageshack.us/img6/7571/mathfinitestatemachinedco3.gif

이 말은 일부 주 Q0 (옆에 시작 기호가있는 사람)에서 시작하면 다른 상태로 갈 수 있다는 것입니다. 각주는 원입니다. 각 화살표는 입력 또는 출력을 나타냅니다 (보는 방법에 따라 다름). 유한 상태 기계를 생각하는 또 다른 방법은 "유효한"또는 "허용 가능한"입력 측면에서입니다. 특정 유한 상태 시스템은 불가능한 특정 출력 문자열이 있습니다. 이를 통해 표현식을 "일치"할 수 있습니다.

이제 Q0에서 시작한다고 가정 해 봅시다. 이제 0을 입력하면 상태 Q1로 이동합니다. 그러나 1을 입력하면 상태 Q2로 이동합니다. 입력/출력 화살표 위의 기호로 이것을 볼 수 있습니다.

Q0에서 시작 하여이 입력을 받는다 고 가정 해 봅시다.

0, 1, 0, 1, 1, 1

이것은 당신이 상태를 겪었다는 것을 의미합니다 (Q0에 대한 입력 없음, 그냥 시작합니다).

Q0-> Q1-> Q0-> Q1-> Q0-> Q2-> Q3-> Q3

이해가되지 않으면 손가락으로 그림을 추적하십시오. Q3은 입력 0과 1 모두에 대해 스스로로 돌아갑니다.

이 모든 것을 말하는 또 다른 방법은 "주 Q0에 있고 0이 Q1로 이동하지만 1 Q2로 이동한다면"입니다. 각 상태에 대해 이러한 조건을 만드는 경우 주 머신을 정의하는 것이 거의 완료됩니다. 상태 변수가있는 다음 입력을 펌핑하는 방법 만 있으면 기본적으로 존재하는 것입니다.

자, 조엘의 진술과 관련하여 이것이 중요한 이유는 무엇입니까? 글쎄, "모두를 지배하기 위해 하나의 진정한 정규 표현"을 구축하는 것은 매우 어려울 수 있으며 수정을 유지하기가 어려울 수 있습니다. 또한 경우에 따라 더 효율적입니다.

물론 상태 기계에는 다른 많은 용도가 있습니다. 이것이 작은 방법으로 도움이되기를 바랍니다. 나는 이론에 들어 가지 않았지만 FSM에 관한 흥미로운 증거가 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top