코드의 자료구조가 이해되지 않습니다.

rlj1202의 이미지

https://swtch.com/~rsc/regexp/nfa.c.txt

위 주소의 코드를 보고 있었는데 이해가 되지 않는 부분이 두군데 있습니다. 일단 코드를 보면

/*
 * Since the out pointers in the list are always 
 * uninitialized, we use the pointers themselves
 * as storage for the Ptrlists.
 */
union Ptrlist
{
	Ptrlist *next;
	State *s;
};
 
/* Create singleton list containing just outp. */
Ptrlist*
list1(State **outp)
{
	Ptrlist *l;
 
	l = (Ptrlist*)outp;
	l->next = NULL;
	return l;
}

State의 정의 부분은 다음과 같습니다.

typedef struct State State;
struct State
{
	int c;
	State *out;
	State *out1;
	int lastlist;
};

일단, Ptrlist의 목적은 이름에서 알 수 있듯이 무언가의 리스트 이겠거니 싶었습니다. 그런데 Ptrlist는 union 타입이란 말이죠? 이해가 되지 않아서 그림을 그려봤는데 더 이해가 되지 않습니다.

음... union 타입이니까 Ptrlist의 맴버 변수 타입인 Ptrlist* 혹은 State* 둘 중 하나만 의미가 있겠다고 생각했습니다. 그렇게 생각하고 그림을 그려보았습니다. 만약 제가 그림을 제대로 그렸다면??? 저 자료구조는 전혀 리스트가 아닙니다. 그냥... 삼중 사중 포인터라는 느낌밖에 없습니다.

일단 그렇다 치고 list1() 함수도 이해할 수 없었습니다. 주석으로는 새로운 리스트를 만든다는데 함수에서 하는 일이라고는 그냥 type conversion 밖에 없습니다. 게다가 State** 를 Ptrlist* 로 캐스팅합니다. 이것도 이해가 안되서 그림을 그려봤는데 더 이해가 되지 않습니다.

일단 State** 값을 매개변수로 받았고 그 값을 Ptrlist* 변수에 넣었으니 결과는 위와 같을 것이라고 생각했습니다. 그렇다면 State* == Ptrlist 라는 것인가요???

kldp회원분들께 코드 해석을 ㅇ...요청드립니다.

gkgkgk의 이미지

automata state machine 이론 같네요

rlj1202의 이미지

네, 오토마타를 공부하면서 찾은 코드입니다.

raymundo의 이미지

질문글 덕분에 신기한 코드 저도 배워가네요.

말로 설명하기는 힘든데, 예를 들어 "a|b" 라는 정규식을 NFA로 변환할 때

             +--------+   a
          +->+ state1 +--+
          |  +--------+  |
 +-----+  |              |   +-----+
>+Split+--+              +-->+Match|
 +-----+  |              |   +-----+
          |  +--------+  |
          +->+ state2 +--+
             +--------+   b

위와 같이 변환되겠죠.

그러면 state1 의 out 과 state2 의 out 필드가 동일하게 Match state 를 가리켜야 하는데, 두 out 필드를 보관하는 일과, 일괄적으로 Match를 가리키게 하는 과정을 저 Ptrlist 리스트를 써서 하고 있네요.

"a|b"를 일단 후위표기힌 "ab|"로 바꾼 다음에, a, b, |를 각각 읽은 시점에 스택에 들어가 있는 Frag구조체의 out 필드는 저 state1과 state2의 out 필드의 리스트입니다.

State*
post2nfa(char *postfix)
{
...
    for(p=postfix; *p; p++){
    ...
    }
/*
입력 데이터가 더 이상 없음
 
이 시점에 
stack 배열에는 하나의 Fragment가 있고, 그 Fragment의 start는 Split state를 가리키고 있고, out은 다음과 같이 리스트를 유지
 
stack[0].out --> state1의 out --> state2의 out --> NULL
 
이제 이 두 out 필드가 모두 Match state를 가리키도록 하는게 patch()의 일
*/
    patch(e.out, &matchstate);
 
/*
 patch 를 하고 나면
 
  state1의 out --> Match state
  state2의 out --> Match state
*/

좋은 하루 되세요!

rlj1202의 이미지

그림으로 그려보고나서 답변을 이해했네요. 그러니까, 말그대로 State* 주소값 리스트(Ptr list) 인데, union을 사용해서 일종의 State*와 Ptrlist*를 alias로 만들었다? 고 볼 수 있는 것 같네요. 정말... 공간 활용을 제대로 한 것 같아요.

익명 사용자의 이미지

덕분에 저도 좋은거 배워 갑니다.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.